Assignment 9
MATH 239 Fall 2022
Due: Friday, December 2 at 10:00am
A-9-1. Let d be a non-negative integer. A graph G is d-degenerate if every subgraph of G contains a
vertex of degree at most d.
Let G be a graph on n vertices.
(a) {2 marks} Prove that G is a forest if and only if G is 1-degenerate.
(b) {4 marks} Prove that G is d-degenerate if and only if there exists an ordering v1, . . . , vn
of V (G) such that
|NG(vi) ∩ {v1, . . . , vi?1}| ≤ d
for all i ∈ {2, . . . , n}.
A-9-2. {4 marks} Let d be a non-negative integer. Prove that if G is a d-degenerate graph, then G is
(d+ 1)-colourable.
A-9-3. {4 marks} Let G be a graph and let E1, . . . Er be a partition of E(G). For each i ∈ {1, . . . , r},
let Gi be the graph with V (Gi) = V (G) and E(Gi) = Ei. For each i ∈ {1, . . . , r}, let ki be a
positive integer such that Gi is ki-colourable. Let k =
∏r
i=1 ki.
Prove that G is k-colourable.
A-9-4. (a) {4 marks} Let G be a graph and letM be a maximal matching of G (that is, a matching
that is not a proper subset of any bigger matching of G). Let N be a maximum matching
of G.
Prove that |N | ≤ 2|M |.
(b) {2 marks} For each positive integer k, provide an example of a graph G, a maximal
matchingM of G and a maximum matching N of G such that |M | = k and |N | = 2k.