Section 4: Bipartite graphs

Question 1

Bipartite graph

Answer 1

A graph G = (V, E) with the property that V can be partitioned into two disjoint sets V1 and V2 such that V = V1 ∪ V2 and every edge has one endpoint in V1 and the other in V2.

Question 2

Bipartition

Answer 2

V can be partitioned into two disjoint sets V1 and V2 such that V = V1 ∪ V2 and every edge has one endpoint in V1 and the other in V2. In this case, we call (V1, V2) a bipartition of V

Question 3

Check whether a given connected graph G = (V, E) is bipartite

Answer 3

a) Pick any vertex v ∈ V, set V1 ={v} and set V2 = ∅.
b) While V1 ∪ V2 6= V, pick a vertex v ∈ V \ (V1 ∪ V2) that has
a neighbour in V1 ∪ V2:
* if v has a neighbour in V1 but no neighbour in V2, add v to V2;
* if v has a neighbour in V2 but no neighbour in V1, add v to V1;
* if v has a neighbour in V1 and a neighbour in V2, return “NOT BIPARTITE.”
c) Return “BIPARTITE” and the bipartition (V1, V2).

Question 4

Check whether a general graph is bipartite

Answer 4

Apply the procedure to each connected component in turn: a graph is bipartite if and only if every connected component is bipartite.

Question 5

Complete bipartite graph

Answer 5

A graph G = (V, E), where V
can be partitioned into disjoint sets V1 and V2, with V = V1 ∪ V2, such that E = {v1v2 : v1 ∈ V1, v2 ∈ V2}.

Question 6

Complete bipartite graph notation

Answer 6

We write Kp,q for the complete bipartite graph whose vertex sets have size p and q respectively

Question 7

Closed walk of length p (for some natural number p ≥ 3)

Answer 7

a sequence of vertices w1, . . . , wp such that wiwi+1 is an edge for every 1 ≤ i ≤ p − 1, and wpw1 is an edge; unlike a cycle, a closed walk may contain the same vertex more than once.

Question 8

Distance between vertices u and v in G

Answer 8

written d(u, v) and is the number of edges in the shortest path from u to v.

Question 9

Characterisation of bipartite graphs in terms of the cycles they contain (Theorem)

Answer 9

A graph G is bipartite if and only if it contains no cycle of odd length as a subgraph.

Question 10

Matching

Answer 10

A matching in a graph is a set of independent edges, that is a set of edges so that no two edges in the set have a common endpoint

Question 11

Perfect matching

Answer 11

A perfect matching is a matching that covers all the vertices, i.e. in which every vertex is incident with exactly one edge in the matching.

Question 12

N_G(X)

Answer 12

If X is a set of vertices in a graph G, we write N_G(X) for the set of
vertices in G that have at least one neighbor in X

Question 13

Hall’s condition

Answer 13

if there is a perfect matching in the graph G with bipartition (U, W): for all U’ ⊆ U, we have |NG(U’)| ≥ |U’|.