Book contents
- Frontmatter
- Contents
- Preface
- Notation
- Chapter 1 Basic concepts
- Chapter 2 Introduction to bipartite graphs
- Chapter 3 Metric properties
- Chapter 4 Connectivity
- Chapter 5 Maximum matchings
- Chapter 6 Expanding properties
- Chapter 7 Subgraphs with restricted degrees
- Chapter 8 Edge colourings
- Chapter 9 Doubly stochastic matrices and bipartite graphs
- Chapter 10 Coverings
- Chapter 11 Some combinatorial applications
- Chapter 12 Bipartite subgraphs of arbitrary graphs
- Appendix
- References
- Index
Chapter 6 - Expanding properties
Published online by Cambridge University Press: 05 November 2011
- Frontmatter
- Contents
- Preface
- Notation
- Chapter 1 Basic concepts
- Chapter 2 Introduction to bipartite graphs
- Chapter 3 Metric properties
- Chapter 4 Connectivity
- Chapter 5 Maximum matchings
- Chapter 6 Expanding properties
- Chapter 7 Subgraphs with restricted degrees
- Chapter 8 Edge colourings
- Chapter 9 Doubly stochastic matrices and bipartite graphs
- Chapter 10 Coverings
- Chapter 11 Some combinatorial applications
- Chapter 12 Bipartite subgraphs of arbitrary graphs
- Appendix
- References
- Index
Summary
This chapter is devoted to bipartite graphs which have the property that any subset of vertices, from one of the colour classes, has a neighbour set which is at least as large as itself, be it by some additive or multiplicative factor. We shall see that such graphs have a very useful structure, and a variety of applications.
Graphs with Hall's condition
We begin by considering bipartite graphs with bipartition (V1, V2) which satisfy the condition |N(A)| ≥ |A| for every A ⊆ V1 (where N(∅) = ∅). Graphs with this property arise very often in practice. Many practical problems can be reformulated as problems about finding a matching M such that every vertex in V1 is incident with an edge in M. Such a matching is called a matching of V1 into V2. The ‘marriage problem’, which we have already considered in Section 5.1, is one of many examples.
It is clear that for us to hope to find a matching of V1 into V2 we must have |N(A)| ≥ |A| for every A ⊆ V1. Remarkably, as the following result of Philip Hall (1935) shows, this condition is also sufficient.
Theorem 6.1.1 (Hall's Theorem) Let G be a bipartite graph with bipartition (V1, V2). Then G has a matching of V1 into V2 if and only if |N(A) ≥ |A| for every A ⊆ V1.
- Type
- Chapter
- Information
- Bipartite Graphs and their Applications , pp. 75 - 96Publisher: Cambridge University PressPrint publication year: 1998