MIDTERM

MATH 38, SPRING 2012

SOLUTIONS
1. [20 points]
(a) Prove that if G is a simple graph of order n such that (G) + (G) n 1, then G is connected.
(Hint: Consider a vertex of maximum degree.)

(b) Show that this bound is sharp (i.e. there is no smaller way to bound (G) + (G) below and
guarantee G is connected).
Proof. For part (a), consider v V (G) with d(v) = (G). We can show that any vertex which is not a
neighbor of v has at lease one neighbor in common with v as follows: Suppose u V (G) is not adjacent
to v, and consider N (u) N (v). Since |N (u)| (G), |N (v)| = (G), and |N (u) N (v)| n 2 (the
size of V (G) {u, v}), we have
|N (u) N (v)| = |N (u)| + |N (v)| |N (u) N (v)|
(G) + (G) (n 2)
n 1 (n 2) = 1.
So all vertices in G have distance at most two from v, and thus G is connected.
For (b), consider G = Kn2,1 + P1 . Since (G) + (G) = n 2 + 0 and G is not connected, the bound
in (a) is sharp.

2. [20 points] Let d1 d2 dn 1 be an integer sequence.
(a) If this is a degree sequence for a forrest, calculate S(n, k) =
vertices n and the number of components k.

i di

in terms of the number of

(b) P
With S(n, k) as in part (a), show that every integer sequence d1 d2 dn 1 with
i di = S(n, k) is the degree sequence for a forrest with k components.
(Hint: We already know the case when k = 1; you are welcome to cite that without proof.)

Proof. I wrote up a few solutions, for which these two lemmas come up a few times.
Lemma 1. The following are equivalent:
A. G is a forrest (acyclic) with k components.
B. G is acyclic with n k edges.
C. G has n k edges and k components.
D. G is loopless and every pair of vertices either has a unique path between them, or they are not
connected.
The proof is by considering each component individually, and seeing that it is a tree.
1

MATH 38, SPRING 2012

Lemma 2. If a strictly positive integer sequence of length n sums to 2n 2k, then it must contain at
least 2k 1s.
Were now ready to proceed.

(a) By Lemma 1, G has n k edges and therefore its degrees sum to 2(n k).
(b) The goal is, if you are given n integers satisfying
d1 d2 dn 1

and

n
X

di = 2(n k),

i=1

to find some forrest with d(vi ) = di (for free, that forrest willl have k components by (a)). I have
collected here several of your ideas for part b.
Method 1. Idea: Construction + Existance. Take out a clear-cut, and build
a tree.
P
Construct a forrest G as follows: Set V (G) = {v1 , . . . , vn }. Since ni=1 di = 2(n k)
and di 1, we have dni = 1 for i = 0, . . . , 2k 1 (the last 2k values, by Lemma 2).
So connect vn2i to vn2i+1 for i = 0, . . . , k 1 to form k 1 P2 s. For the remaining
n 2k + 2 degrees, they sum to
n2k+2
X

di = 2(n k) 2(k 1) = 2((n 2k + 2) 1)

i=1

and so there is some tree on v1 , . . . , vn2k+2 which satisfies d(vi ) = di . Use these vertices
to form such a tree, and the result is a forrest with k 1 + 1 = k components.
Method 2. Idea: Construction. Use the Pr
ufer code.
We know n 2k since di 1. Make a list of length n 2k with values from {1, . . . , n}
with di 1 is. Use the algorithm for trees, except now at the last step, there will be
2k unmarked vertices. Pair these up as you like, adding a single edge between pairs.
The method guarantees that you have a forrest with n k edges, which therefore has
k components. (With more thought, this should imply that there are no more than
Qk1 n2i

Q(n2k)!
such trees [the last step of pairing them up is a little funny]).
i=1
2
(di 1)!
i

Method 3. Idea: Existence + tinkering. Theres some graph with this degree sequence,
so manipulate
any such graph until it is the desired forrest.
P
Since i di is even, there is some graph on n vertices with d(vi ) = di . Let G be one such
graph. Since G has n k edges, G has at least k components. If all the components in G
are acyclic, then G has exactly k components and G is a forrest (Lemma 1). Otherwise,
find some component H which has a cycle, and let e be an edge in that cycle with
endpoints u and v. Let e0 be and edge in a different component H 0 with endpoints u0 and
v 0 . Then G e e0 + uu0 + vv 0 is a graph with one fewer component, since e was not
a cut edge in H, and everything in H 0 is now connected to H (either through u0 or v 0 ).
Furthermore, this two-switch preserved the degrees of all vertices in G. By induction on
the number of components, it is possible to arrive at a graph F with dF (vi ) = di which
has k components (and is therefore acyclic and a forrest).

MIDTERM

Method 4. Idea: Induction. Add a total of 2 somehow to the di s, and use induction to
build a forrest with one too many edges and one too few components. Then
figure out how to delete an edge and get back to the desired forrest.
P
Fix n. If ni=1 di = 2(n 1), then we know there is some tree with d(vi ) = di . Otherwise,
assume that k > 1 and that for any k 1 if
n
X
0
0
0
d1 d2 dn 1
and
d0i = 2(n (k 1)),
i=1

then there is a forrest on n vertices with d(vi ) = d0i .

P
Try 1: P
Let d01 = d1 + 2 and d0i = di for i = 2, . . . , n. Then if ni=1 di = 2(n k), we have
n
0
i=1 di = 2(n k) + 2 = 2(n (k 1)). So there is some forrest G with k 1
components with d(vi ) = d0i . Since d01 > 2, we know v1 has at least 2 neighbors, u
and w. Delete the edges v1 u and v1 w, and add the edge uw. This has preserved
the degree of u and w, it has dropped the degree of v1 by 2, and it has preserved
the acyclic nature of G (since it simply took the unique uw path and shortened
it by one). So the result is a graph G0 with d(vi ) = di , and which is acyclic, and
is therefore a forrest with k components.
Try 2: Let d01 = d1 + 1 and d02 = d2 + 1. Again. by induction, there is some forrest with
k 1 components with d(vi ) = d0i .
Case 1: v1 is adjacent to v2 in G. Delete v1 v2 .
Case 2: v1 is in the same component as v2 , but is not adjacent. Then consider
the v1 , v2 path in G. Let u1 and u2 be their respective neighbors on this path.
Perform the following transformation:
Delete v1 u1 and v2 u2 . This has separated the component into three pieces,
one with v1 , one with v2 , and one with neither.
Splice in the component without v1 or v2 into anywhere else by picking any
other edge ab (there is at least one since v1 had at least two neighbors),
deleting it and adding the edges au1 and bu2 . This restores the degrees of
u1 and u2 , as well as the original number of components.
Case 3: vi is in a different component than v2 . Let u1 and u2 be neighbors of v1
and v2 respectively (they exist because d(vi ) 1). Exchanges the edges u1 v1 and
u2 v2 for u1 u2 . This preserves the degrees of u1 and u2 and lowers the degrees of
v1 and v2 by 1, as desired.
In all three cases, the result is a graph with one more component and one fewer
edge, and so is a forrest with k components.
Method 5. Idea: Constuction + tinkering. Build a tree T on n+ 1 vertices so that T vn+1
is a forrest with the desired degree sequence.
Form a tree that corresponds to the following Pr
ufer code:
i. For i = 1, . . . , k 1 alternate di occurrences of i with one occurrence of n + 1;
ii. list di 1 ocurrences of i for i = k + 1, . . . , n;

MATH 38, SPRING 2012

iii. list dk ocurrences of k.

For example, if your integer sequence is
d1 = 5, d2 = d3 = 3, d4 = d5 = d6 = 2, d7 = = d17 = 1,
|
{z
}
11 ones

then n = 17, k = 3, and the resulting code is

1, 1, 1, 1, 1, 18, 2, 2, 2, 18, 4, 5, 6, 3, 3, 3 .
| {z }
| {z }
| {z }
d1 1s

d2 2s

d3 3s

The result will be a list with n 1 values from the elements {1, . . . , n + 1} and so will
result in a tree T with n + 1 vertices.
a. For i = 1, . . . , k, since i appears di times, we have dT (vi ) = di + 1;
b. for i = k + 1, . . . , n, since i appears di 1, we have dT (vi ) = di ; and
c. since n + 1 appears k 1 times, we have dT (vn+1 ) = k.
d. Since n + 1 appears each time the each of 1, . . . , k 1 disappears from the list when
building T , and so n + 1 is adjacent to v1 , . . . , vk1 .
e. Once n + 1 disappears from the list, it will not be used until no other values are
available. This will not occur until the final step, when only vk and vn+1 remain to
be connected. So in T , vn+1 is adjacent, in total, to v1 , . . . , vk1 . (The best picture is
going through the procedure of building the example above, and then observing the
adjacencies of v18 ).
Therefore, the induced graph T {vn+1 } is a forrest on v1 , . . . , vn with k components with
d(vi ) = di (removing k edges from a T yields a forrest with k + 1 components; removing
the edges incident to vn+1 and then vn+1 itself gives the desired result).
Method 6. Idea: Construction. Build it explicitly, not relying on the Pr
ufer code.
Well construct a forrest with d(vi ) = di via a series of graphs with weighted vertices as
follows. At each step, every vertex in the graph G has a non-negative integer weight. At
the end, the weights will all be 0 and G will the the desired forrest.
Step 1: Place the 2k vertices vn 2k + 1, . . . , vn in G, and weight them with 1.
Justification: We know there are at least 2k ones in the integer sequence, so
this can be done.
Step 2: Add v1 , v2 , . . . , vn2k sequentially as follows:
When adding vi , look for a vertex vj already in G (so j < i or j > n 2k)
with the largest nonzero weight. Add the edge vi vj , and update the weight of
vj by subtracting 1. Weight vi with di 1. When breaking ties, add vi to a
component with the fewest vertices with nonzero weight.
Justification: In order to be able to add the next vertex, you only require that
some vertex in G has weight at least 1, which is equivalent to showing that the
sum of the weights is positive. The weight is a working tally of
wt(vi ) = #(edges vi needs) #(edges vi has) = di dG (v).

MIDTERM

Furthermore, at each step G is a forrest with 2k components. So by (a),

X
dG (v) = 2(2k + i 2k) = 2i.
vV (G)

Therefore we require that, for i = 1, . . . , n 2k,

0

X
vi V (G)

wt(vi ) =

(di dG (vi ))

vi V (G)

= 2k +

i
X

di

j=1

dG (vi )

vV (G)

i
X
= 2k +
dj 2i
j=1

= 2k +

i
X

(dj 2).

j=1

P
But ij=1 (dj 2) is a non-decreasing function in i while di 6= 1 and then is a
decreasing function (so the global minimum happens at an endpoint). When
i = 1, wt(v1 ) is at least 1 (since d1 1 and k 1); when i = n 2k,
!
n2k
n
X
X
2k +
(dj 2) = 2k +
di 2k 2(n 2k)
j=1

i=1

= 2(n k) 2(n 2k)

= 2k.
So we can always add the next vertex.
Step 3: When all of the vertices have been added, there will be one vertex with weight
1 in each of the 2k components. Pair up the components and add an edge
between weight 1 vertices in each pair.
Justification: Revisiting the above calculation, we showed that at the moment
when the last vertex is added,
X
wt(v) = 2k.
vV (G)

There can be no more than 2k vertices with nonzero weight since weights are
non-negative. There also can be no fewer: We always added a new vertex to
an old vertex of highest available weight, and (aside from the first 2k vertices)
we added vertices in decreasing order of initial weight. Therefore, the only way
for one component to have no non-zero weight vertices is for all vertices in G
to be of weight at most 1. Moreover, by how we break ties, if some component
is closed, no other component can have more than one vertex of weight 1
(or we would have closed a vertex in that component first). So the 2k weights
must be spread evenly across the components.
At the end, every vertex has weight 0 (and so d(vi ) = di ). So you have a graph with n k
edges, and exactly k components, so G is a forrest.

MATH 38, SPRING 2012


3. [15 points] Recall that a tournament is a directed complete graph, i.e. for every two vertices u and v,
either there is an edge from u to v or there is an edge from v to u (but not both). Show that every
tournament has a spanning path. (Hint: Can a non-spanning path be exchanged for a longer path?)
Proof. Consider a maximal non-spanning path P = p1 p2 p` in a tournament G. Then for
any u
/ V (P ), we have p1 u and u p` (because P was maximal). So there exists some pair pi
and pi+1 satisfying pi u pi+1 , and hence
p1 pi u pi+1 . . . p`
is a path of length greater than P . Therefore, any maximum path in G is spanning.

4. [15 points] Show that a m-regular simple graph G has a decomposition into copies of K1,m if and only
if G is bipartite.
Proof. If G is bipartite, with partites X and Y , then since G is m-regular,
for each v X,
G[{v} N (v)]
= K1,m .
Every edge in G appears as an edge incident to some v X and every u Y appears in a neighborhood
of some v (since d(u) = m > 0),Sand no edge appears incident
to more than one v X (because G is
S

bipartite. So G decomposes as vX G[{v} N (v)] = vX K1,m .

If G decomposes into copies of K1,m , then let X be the set of vertices occurring as a center of
some star, and let Y be the set of vertices occurring as leaves of some star. The decomposition implies
that X Y = V (G). A priori, these two sets might not be disjoint, but since G is m-regular, no vertex
in G can have more than m neighbors. Therefore, no vertex in X can also be a vertex of Y (or vice
versa), so X Y =. Again, by the decomposition, two vertices are only adjacent if one is in X and
one is in Y (they are adjacent in some star), and so X, Y forms a bipartition of G.

5. [10 points] Give an example of a weighted graph G with n(G) = 4 where. . .
(a) . . . executing Dijkstras algorithm from any vertex will give a minimum weight spanning tree.
(b) . . . executing Dijkstras algorithm from any vertex will not give a minimum weight spanning tree
(no matter where you start it, you will not get a minimum-weight spanning tree).
(c) . . . every minimum weight spanning tree has the property that the distance between any two
vertices in G is the same as the distance between those two vertices in the tree.
(d) . . . every minimum weight spanning tree has the property that the distance between some two
vertices in G is strictly less than the distance between those two vertices in the tree (i.e. all
shortest paths are lost between some pair of vertices).
Answer. For (a) and (c), pick any weighted tree on four vertices (there is exactly one spanning tree,
and it is of minimum weight, and contains all paths present in G). For (b), take the K4 , drawn as a
square with two diagonals. Weight the two horizontal edges by 2, the two verticals by 4, and the two
diagonals by 5. The minimum weight spanning tree has weight 2 + 2 + 4 = 8, but Dijkstras algorithm
will give a tree of weight 2 + 4 + 5 = 11 from any vertex. For (d), let G = C4 with equal weights on all
edges. Any spanning tree is a path P , and the endpoints of the path will be farther apart in P than
they are in G.

MIDTERM

6. [10 points] List 8 or more (up to 20) facts about the Petersen graph.
(Show me your diversity of knowledge about graph theory thus far. What kinds of questions does one
ask about a graph? In addition to giving properties that the Petersen graph has, its also legitimate to
list properties that the Petersen graph doesnt have, or to count things having to do with the Petersen
graph. Eight legitimately diverse facts, including a couple of non-trivial statements, will receive full
credit; if in doubt, list more or ask.)
1. It has 10 vertices (size 2 subsets of [5]) and 15 edges (E(G) = {uv | |u v| = 0}).
2. Its three-regular.
3. It has girth 5 (no cycles of length 1-4), and various other facts about cycles of length longer.
4. It decomposes in various interesting ways, but not into claws, and not into edge-disjoint spanning
trees.
5. Its not bipartite.
6. Its chromatic number is 3.
7. Its simple.
8. There are 5! isomorphic graphs on [10] to the Petersen graph.
9. Its connected, and admits an orientation which yields a strongly connected digraph.
10. It has a spanning path, and some spanning caterpillars, and some large number of spanning trees.
11. It has no Eulerian path or circuit (too many odd vertices).
12. The shortest non-extendable trail has length 8 (since it has to contain a cycle, and then a walk
between vertices in that cycle).
13. It represents one isomophism class with its degree sequence, but not the only such class. In fact,
the graph generated by the algorithm for graphic sequences generates a different one (one of the
bipartite graphs) and the algorithm for simple graphs generates a third (5 P2 s with loops at each
vertex).
14. It has several perfect matchings. Therefore, any closed walk will have to duplicate at least five
edges.
15. Its not planar.
16. It is the union of 5-cycles, and so has no cut-edges and no cut-vertices.
17. It has radius and diameter 2, and therefore is its own center.
18. Its complement also has diameter and radius 2.
19. Every pair of non-adjacent vertices share a unique neighbor.
20. Someone more ambitious than I could write down the adjacency and incidence matrices.

MATH 38, SPRING 2012

7. [10 points] For free: tell me what you like most about graph theory so far (a favorite topic, kind of
problem, way of thinking about things, etc.) or something youve learned related to graph theory
(from class or not) that you enjoy a lot.
Clearly, its you guys that makes this class great for me!!