Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment
MATH 239 A-7-1. {6 marks} Let G = (V,E) be a nonempty graph in which every vertex has degree at least 3. (a) Show that G contains (as a subgraph) a cycle with at least 4 edges. (b) Show that G contains (as a subgraph) a cycle with an even number of edges. A-7-2. {7 marks} (a) Let T = (V,E) be a tree with p1 vertices of degree one and p3 vertices of degree 3, and no vertices of other degrees. Show that p3 = p1 − 2. (b) Let T = (V,E) be a tree with p1 vertices of degree one and no vertices of degree 2. Show that |V | ≤ 2p1 − 2with equality if and only if every vertex has degree either 1 or 3. A-7-3. {7 marks} Let G = (V,E) be a connected graph, and let T1 and T2 be two spanning trees of G. Prove that for every edge e ∈ E(T1) of T1, there is an edge f ∈ E(T2) of T2 such that T ′ = (T1 ∖ e) ∪ {f} is also a spanning tree of G.