MATH 239代写、代写C++/Python程序

日期：2022-12-03 12:28

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.