Math 108 Homework 1 Solutions

Problem 1B
Suppose that G is a simple graph on 10 vertices that is not connected. Prove that G has
at most 36 eges. Can equality occur?
Proof. Let v be one of the vertices of G. Let A be the connected component of G
containing v, and let B be the remainder of G, so that B = G \ A. Let a be the number
of vertices in A, and b the number of vertices in B. Since G is not connected, both A and
B are nonempty, so a, b ≥ 1, and since G has ten vertices, b = 10 − a. By the definition
of a connected component, there are no edges in G between vertices in A and vertices in
B, so that the number of edges in G is bounded above by sum of the numbers of edges in
the complete graphs on the vertices of A and of B.
The complete graph with n nodes has n(n − 1)/2 edges, so that the number of edges
in G is bounded above by

max a(a − 1)/2 + (10 − a)(10 − a − 1)/2

a∈{1,2,...,9}

a2 − a + 100 − 20a + a2 − 10 + a
= max
a∈{1,2,...,9} 2
2
= max a − 10a + 45
a∈{1,2,...,9}

It is readily verified that this maximum occurs for a = 1 (or a = 9), and takes the value
36. Thus G has at most 36 edges. Moreover, equality can occur, if G is the union of the
complete graph on 9 vertices with an extra lone vertex not adjacent to any other.
Problem 1C
Show that a connected graph on n vertices is a tree if and only if it has n − 1 edges.
Proof.
(⇒) Suppose that G is a tree with n vertices. Let v1 be a given vertex in G. For
1 ≤ m < n, let Vm = {v1 , ..., vm }, and let vm+1 be a vertex in G which is not contained
in Vm but which is adjacent to one of the vertices in Vm . Also, let Gm be the induced
subgraph of G on the vertex set Vm . (Note that the manner in which vm+1 is selected
implies that Gm is connected for all m.) Then I claim that for each 1 ≤ m ≤ n, Gm has
m − 1 edges.
I prove this by induction. The claim is trivial for m = 1. Suppose the claim holds
for m = k, i.e. that Gk has k − 1 edges. Then, since Gk+1 ⊇ Gk , and Gk+1 is connected,

1
 2

Gk+1 contains all of the k − 1 edges that Gk contains, and also contains at least one edge
incident to vk+1 , so that Gk+1 contains at least k edges. Suppose that Gk+1 contains more
than one edge incident to vk+1 . Thus, Gk+1 contains the edges (vk+1 , va ) and (vk+1 , vb )
for some a 6= b, a, b ≤ k. Since Gk is connected, there is a path from va to vb in Gk , and
appending the edges (vb , vk+1 ) and (vk+1 , va ) closes a loop in Gk+1 . Since Gk+1 ⊆ G, this
shows that G is not a tree, a contradiction. Thus, Gk+1 has precisely k edges. Since this
holds for Gn = G, we may conclude that if G is a tree with n vertices, then G has n − 1
edges.
(⇐) Suppose that G is a connected graph with n vertices which is not a tree. Let the
vm , Vm and Gm be as defined in the first direction of the proof. The number of edges in
G1 is zero, and by similar arguments to those given above, the number of edges in Gm+1 is
at least one greater than the number of edges Gm . Let M be the smallest positive integer
such that GM contains a loop. Then vM must be one of the vertices involved in the loop,
and as a result, must be adjacent to at least two of the vertices in VM −1 . As a result, the
number of edges in GM is at least two greater than the number of edges in GM −1 . Thus,
the number of edges in Gn = G is at least n − 2 + 2 = n > n − 1. Thus, if G is a connected
graph with n vertices which is not a tree, G does not have n − 1 edges.
Problem 1G
Show that a finite simple graph with more than one vertex has at least two vertices with
the same degree.
Proof.
First, suppose that G is a connected finite simple graph with n vertices. Then every
vertex in G has degree between 1 and n − 1 (the degree of a given vertex cannot be zero
since G is connected, and is at most n − 1 since G is simple). Since there are n vertices in
G with degree between 1 and n − 1, the pigeon hole principle lets us conclude that there
is some integer k between 1 and n − 1 such that two or more vertices have degree k.
Now, suppose G is an arbitrary finite simple graph (not necessarily connected). If
G has any connected component consisting of two or more vertices, the above argument
shows that that component contains two vertices with the same degree, and therefore G
does as well. On the other hand, if G has no connected components with more than one
vertex, then every vertex in G has degree zero, and so there are multiple vertices in G
with the same degree.
Problem 2A
Find the six nonisomorphic trees on 6 vertices, and for each compute the number of
distinct spanning trees in K6 isomorphic to it.
See Figure 1 for the six isomorphism classes. These were obtained by, for each k =
2, 3, 4, 5, assuming that k was the highest degree of a vertex in the graph. For k 6= 3,
there is precisely one connected tree on 6 vertices such that the largest degree is k, and
for k = 3, there are the three possibilities depicted.
 3

Proof.

Figure 1: The six isomorphism classes of simple graphs on six vertices.

As noted in the text, the number of distinct spanning trees isomorphic to a given
one of these graphs is equal to 6! divided by the size of the automorphism group of the
graph. Proceeding clockwise from the top left graph, we may compute the order of the
automorphism groups as follows:

1. Any automorphism of the path graphs must send each endpoint (degree 1 vertex)
to an endpoint, and there are only two maps that do that: the identity, and the
map which reverses the path. Thus, this graph has automorphism group of order 2.

2. The top middle graph has precisely one vertex of degree 3, and so this vertex must
be fixed under any automorphism. In addition, the degree one vertices adjacent
to the degree three vertex are closed under the automorphism group, so that there
are only two automorphisms: the identity, and the map which switches these two
vertices (no other map preserves the remaining graph structure).

3. Similar to the above, any automorphism for the top left graph must map each
degree two vertex adjacent to the degree three vertex to another such vertex, and
after this the automorphism is determined. As there are only two such maps, the
automorphism group has order two.

4. Any map which fixes the degree 5 vertex is an automorphism of the bottom right
graph, so that there are 5! = 120 automorphisms of this graph

5. In an automorphism of the bottom middle graph, the degree 4 vertex must be

preserved, and the automorphism is entirely determined by the manner in which it
permutes the three degree 1 vertices adjacent to the degree 4 vertex (and each such
 4

permutation induces an automorphism), so that the automorphism group has order

3! = 6.

6. Finally, the automorphisms of the bottom left graph consist of the maps which send
the degree 3 vertices to degree 3 vertices, and preserve the adjacencies to the degree
3 vertices. As there are two degree 3 vertices, and two degree 1 vertices adjacent
to each of these (which can be switched in an automorphism), the automorphism
group has size 23 = 8.

The following table summarizes these results:

Graph Size of Automorphism group Number of isomorphic spanning trees

Top Left 2 6!/2 = 360
Top Middle 2 6!/2 = 360
Top Right 2 6!/2 = 360
Bottom Right 5! 6!/5! = 6
Bottom Middle 3! 6!/3! = 120
Bottom Left 23 6!/23 = 90

Note that the total number of spanning trees (computed by summing the right column of
the table above) is 1296 = 64 , which is consistent with Theorem 2.1 from the text.