Question

9. Let G be a bipartite graph and r ∈ Z>0. Prove that if G is r-regular, then G has a perfect matching.1

10. Let G be a simple graph. Prove that the connection relation in G is an equivalence relation on V (G)

Answer 1

9)Proof:
To prove this we first state a theorem.
(Hall’s Marriage Theorem) Let G be a bipartite graph with bipartition
(A, B). Then, there is a matching M ⊆ G which covers A if and only if |N(X)| ≥ |X| for
every X ⊆ A.

Let G be a r-regular bipartite graph with bipartition (A, B). Let X ⊆ A and let t be
the number of edges with one end in X. Since every vertex in X has degree r, it follows that
r|X| = t. Similarly, every vertex in N(X) has degree r, so t is less than or equal to r|N(X)|.
It follows that |X| is at most |N(X)|. Thus, by Hall’s Theorem, there is a matching covering
A, or equivalently, every maximum matching covers A. By a similar argument, we find that
every maximum matching covers B, and this completes the proof.

10)Proof:
Theorem: Let G = (V, E) be a graph. Then the connectivity relation
over V is an equivalence relation.
Proof: Consider an arbitrary graph G = (V, E). We will prove that
the connectivity relation over V is refexive, symmetric, and
transitive.
To show that connectivity is refexive, consider any v ∈ V. Then
the singleton path v is a path from v to itself. Therefore, v is
connected to itself, as required.
To show that connectivity is symmetric, consider any x, y ∈ V
where x is connected to y. We need to show that y is connected
to x. Since x is connected to y, there is some path x, v₁, …, vₙ, y
from x to y. Then y, vₙ, …, v₁, x is a path from y back to x, so y is
connected to x.
Finally, to show that connectivity is transitive, let x, y, z ∈ V be
arbitrary nodes where x is connected to y and y is connected to
z. We will prove that x is connected to z. Since x is connected to
y, there is a path x, u₁, …, uₙ, y from x to y. Since y is connected
to z, there is a path y, v₁, …, vₖ, z from y to z. Then the path
x, u₁, …, uₙ, y, v₁, …, vₖ, z goes from x to z. Thus x is connected to z,as required.