Midterm Solutions

Math 345, Graph Theory I

Instructor: Matt DeVos

Name (print):

Signature:

Problem Score Value

1 3
2 3
3 6
4 6
5 8
6 4
7 10
8 4
9 6
Total: 50

1
 b k
e h
a g j m
d
c f i `

1. (3 points) Find a maximum matching in the above graph.

a, d, g, j, m (other solutions are possible).

2. (3 points) Find a maximal matching in the above graph which is not maximum.
a, e, h, m (other solutions are possible).

2
Consider the following weighted graph.

11
8 4
10
r 7 6

5 2 9
3
1

3. (6 points) If we use Kruskal’s algorithm to choose a min cost tree, what is the sequence
of edge weights we select?
1, 2, 4, 5, 6, 8

4. (6 points) If we use Dijkstra’s algorithm to choose a shortest path tree for the vertex r
in this graph, what is the sequence of edge weights we select?
5, 1, 7, 8, 6, 4

3
5. (8 points) Prove that every simple k-regular graph without a cycle of length 3 has a path
of length at least 2k − 1. (hint: maximal path)
Choose a maximal path P and assume P has vertex sequence v1 , v2 , . . . , vn . By max-
imality, all neighbours of v1 must be in the set {v2 , . . . , vn }. Furthermore, whenever vi is
a neighbour of v1 with i > 2 it must be that vi−1 is not a neighbour of v1 as otherwise
v1 , vi , vi−1 would form a triangle. It follows from this that n ≥ 2k so P has length at least
2k − 1 as desired.

6. (4 points) Find a simple k-regular graph without a triangle for which the longest path
has length 2k − 1 (hint : look for a triangle-free graph with few vertices)
For every k ≥ 1 the graph Kk,k is simple, k-regular, and has no path of length greater
than 2k − 1 (since it has only 2k vertices).

4
7. (10 points) Let T1 and T2 be spanning trees of G with T1 6= T2 . Prove that there exists
e ∈ E(T1 ) \ E(T2 ) and f ∈ E(T2 ) \ E(T1 ) so that both T1 − e + f and T2 − f + e are spanning
trees.
Choose e ∈ E(T1 ) \ E(T2 ) and let C be the fundamental cycle of e with respect to T2 .
Let u, v be the ends of e and observe that the subgraph T1 − e has exactly two components,
H1 , H2 and we may assume (without loss) that u ∈ V (H1 ) and v ∈ V (H2 ). Now, C − e is
a path from u to v, so there must exist an edge f ∈ E(C − e) so that f has one end in H1
and the other in H2 . It now follows that both T1 − e + f and T2 + e − f are spanning trees,
as desired.

5
8. (4 points) Let G be a bipartite graph with bipartition (A, B) and assume that every
X ⊆ A satisfies |N (X)| ≥ |X|. Define a set X ⊆ A to be tight if |N (X)| = |X|. Prove that
whenever X, X 0 ⊆ A are tight then X ∩ X 0 is also tight.
The key observation is the following inequality which holds for all X, X 0 ⊆ A:

|N (X ∩ X 0 )| + |N (X ∪ X 0 )| ≤ |N (X)| + |N (X 0 )|

If X and X 0 are tight then using this we find

|N (X ∩ X 0 )| + |N (X ∪ X 0 )| ≤ |N (X)| + |N (X 0 )| = |X| + |X 0 | = |X ∩ X 0 | + |X ∪ X 0 |

and since |N (X ∩ X 0 )| ≥ |X ∩ X 0 | and |N (X ∪ X 0 )| ≥ |X ∪ X 0 | we must then have that both

X ∩ X 0 and X ∪ X 0 are tight.

9. (6 points) Use the previous problem to give a new proof of Hall’s Marriage Theorem by
induction on |A|. (hint: let x ∈ A and try to find a good vertex to pair with x).
If there is no tight set, then let x ∈ A, choose y ∈ N (x) and set G0 = G − {x, y}. Now
for every X ⊆ V (G0 ) we have |NG0 (X)| ≥ |NG (X)| − 1 ≥ |X| so by induction, G0 has a
matching covering A − {x} and then adding xy to this yields a matching covering A.
Next suppose that a tight set exists, and choose a minimal tight set X ∗ . Let x ∈ X ∗ and
let y ∈ N (X ∗ ) and set G0 = G − {x, y}. Let X ⊆ V (G0 ) and suppose (for a contradiction)
that |NG0 (X)| < |X|. We must have |NG (X)| = |X|, so X is tight (in the original graph).
Since y ∈ N (X ∗ ) ∩ N (X), we must have X ∩ X ∗ 6= ∅ (otherwise X ∪ X ∗ would violate our
condition). However, then X ∩ X ∗ is tight (by the above problem) and it is a proper subset
of X ∗ and this contradicts our choice.