Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Graph and Network Theory
Math 137A
HOMEWORK 4
(1) Draw the tree whose Pr¨ufer code is (1, 1, 1, 1, 6, 5).
(2) Determine which trees have Pr¨ufer codes that have distinct values in all positions.
(3) Let G be a connected graph which is not a tree and let C be a cycle in G. Prove that the complement of any spanning tree of G contains at least one edge of C.
(4) Suppose a graph G is formed by taking two disjoint connected graphs G1 and G2 and identifying a vertex in G1 with a vertex in G2. Show that τ (G) = τ (G1)τ (G2).
(5) Assume the graph G has two components G1 and G2. Show there is a labeling of the vertices of G such that the adjacency matrix of G has the form
A(G) = A( G1) 0 A(
0
G2)
.
(6) An m-fold path, mPn, is formed from Pn by replacing each edge with a multiple edge of multiplicity m. An m-fold cycle, mCn, is formed from Cn by replacing each edge with a multiple edge of multiplicity m.
(a) Find τ (mPn)(b) Find τ (mCn)
(7) Find τ (K2,3).
(8) Use the Matrix-Tree Formula to compute τ (K3,n).