Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Graph and Network Theory
Math 137A
Math 137A Graph and Network Theory HOMEWORK 3
HOMEWORK 3
(1) Show that for each n ∈ N the complete graph Kn is a contraction of Kn,n.
(2) For n ∈ N, can Kn be a contraction of Km,n if m < n?
(3) The complete tripartite graph Kr,s,t consists of three disjoint sets of vertices (of sizes r, s and t), with an edge joining two vertices if and only if they lie in different sets. Draw K2,2,2. What is the number of edges of K2,3,4?
(4) There are exactly 11 unlabeled trees on seven vertices. Draw these eleven trees, making sure that no two are isomorphic.
(5) Show that every tree containing a vertex of degree k contains at least k leaves.
(6) For two points in R
2
, P1 = (x1, y1) and P2 = (x2, y2), let d : R
2 × R
2 → R be given by d(P1, P2) = |x2 − x1| + |y2 − y1|. Show that d is a metric on R
2
.
(7) For all n ∈ N what is the eccentricity of each vertex of Kn? How many centers does Kn have?
(8) Draw all spanning trees of the graph G.