Chapter 41

Bipartite Graphs and Matrices

Bryan L. Shader

University of Wyoming

An m × n matrix is naturally associated with a bipartite graph, and the structure of the matrix is reflected by the combinatorial properties of the associated bipartite graph. This chapter discusses the fundamental structural theorems for matrices that arise from this association, and describes their implications for linear algebra.

41.1 Basics of Bipartite Graphs

This section introduces the various properties and families of bipartite graphs that have special significance for linear algebra.


A graph G is bipartite provided its vertices can be partitioned into disjoint subsets U and V such that each edge of G has the form {u, υ}, where uU and υ

Get Handbook of Linear Algebra, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.