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.