6.042/18.

062J Mathematics for Computer Science September 28, 2010

Tom Leighton and Marten van Dijk

Problem Set 4 Solutions

Due: Monday, October 4 (7pm)

Problem 1. [15 points] Let G = (V, E) be a graph. A matching in G is a set M ⊂ E

such that no two edges in M are incident on a common vertex.
Let M1 , M2 be two matchings of G. Consider the new graph G0 = (V, M1 ∪ M2 ) (i.e. on the
same vertex set, whose edges consist of all the edges that appear in either M1 or M2 ). Show
that G0 is bipartite.
Helpful definition: A connected component is a subgraph of a graph consisting of some vertex
and every node and edge that is connected to that vertex.
Solution. Proof. Proof by induction on the number of vertices n:
Induction hypothesis: P (n) is defined to be: Let G be a graph with n vertices and
matchings M1 and M2 . Let G0 = (V, M1 ∪ M2 ). Then G0 is bipartite.
Base case: G has only one vertex and so is bipartite. P (1) holds.
Inductive step: We will assume P (n) in order to prove P (n + 1).
Let G be a graph with n + 1 vertices. We will remove a vertex v from G to obtain an n
vertex graph, G1 , with vertex set V1 . If we remove v we will be in one of the following cases:
Case 1: v is in none of the edges in M1 nor M2 .
By our inductive hypothesis we know that since G1 has n vertices and M1 and M2 are
matchings of G1 , then G01 = (V1 , M1 ∪ M2 ) is bipartite. Since G01 is bipartite, there exists a
partition of the vertices into two sets, L and R such that every edge is incident to a vertex in
L and to a vertex in R. We can now add v to either set and obtain a bipartite representation
of G0 .
Case 2: v is in an edge in either M1 or M2 , we will assume, without loss of generality, that
v is in an edge in M1 .
Suppose the edge v − x is in M1 , now remove v − x from M1 to obtain M10 .
Now by our inductive hypothesis we know that since G1 has n vertices and M10 and M2 are
matchings of G1 , then G01 = (V1 , M10 ∪ M2 ) is bipartite. Since G01 is bipartite, there exists a
partition of the vertices into two sets, L and R such that every edge is incident to a vertex
in L and to a vertex in R.
We know that the vertex x is in either L or R. We can just add vertex v to the other set,
along with edge v − x, and we obtain a valid partitioning of L and R for our graph G0 .
2 Problem Set 4

Case 3: v is in both M1 and M2

Suppose the edge v − x is in M1 and v − y is in M2 , now remove those edges from M1 and
M2 to obtain M10 and M20 .
Now by our inductive hypothesis we know that since G1 has n vertices and M10 and M20 are
matchings of G1 , then G01 = (V1 , M10 ∪ M20 ) is bipartite. Since G01 is bipartite, there exists a
partition of the vertices into two sets, L and R such that every edge is incident to a vertex
in L and to a vertex in R.
If x and y in the same set, either L or R, then we can just add v to the other set, and add
edges v − x and v − y to obtain G0 . So our graph remains bipartite.
If x and y are on different sides of L and R, then either x and y are in the same con-
nected component or they are in different connected components. If x and y are in different
connected components, then each connected component has a corresponding set of L and
R vertices, such that there are edges only within that component. Let’s say that the first
component has left and right vertices in the set L1 and R1 , and the second component has
sets L2 and R2 , where L = L1 ∪ L2 and R = R1 ∪ R2 . Now if we swap L1 and R1 – that
is we define L = R1 ∪ L2 and R = L1 ∪ R2 – then our graph will remain bipartite, as there
were edges only within the connected components. But after the swapping x and y will be
in the same set, L or R, and as before we can just add v to the other set to get a bipartite
graph for G0 as desired.
Now we will show that it is impossible for x and y to be on opposite sides and in the same
component.
Suppose for a contradiction that x and y are in the same connected component and x and y
are both in L. Then since they are in the same connected component there is a path from
x to y say x − v1 , v1 − v2 , . . . , vk − y, where k is even. Then the edges x − v1 and v2 − v3 ,
v4 − v5 , . . . , vk − y must all be in the same matching (otherwise we will have two edges
incident on the same vertex in the same matching). This is a contradiction since our original
M1 cannot have any edge with x and M2 cannot have any edge with y (since a matching has
only one edge incident to a vertex). So this cannot be the case and x and y must be on the
same side.
Hence we conclude that in all cases G0 is bipartite.
Therefore by induction our claim holds.


Problem 2. [20 points] Let G = (V, E) be a graph. Recall that the degree of a vertex
v ∈ V , denoted dv , is the number of vertices w such that there is an edge between v and
w.

(a) [10 pts] Prove that X

2|E| = dv .
v∈V
Problem Set 4 3

Solution. Let S = {(e, v) ∈ E × V : e is incident on v}.

Count the elements in S as follows
X
|S| = |{v : (e, v) ∈ S}| = 2|E|
e∈E

and also as X X
|S| = |{e : (e, v) ∈ S}| = dv .
v∈V v∈V

The result follows.

Once can also prove it by induction on |E|. You should try to. 

(b) [5 pts] At a 6.042 ice cream study session (where the ice cream is plentiful and it helps
you study too) 111 students showed up. During the session, some students shook hands with
each other (everybody being happy and content with the ice-cream and all). Turns out that
the University of Chicago did another spectacular study here, and counted that each student
shook hands with exactly 17 other students. Can you debunk this too?

Solution. Assume that the study is accurate. Define a graph G = (V, E) with students as
vertices and put an edge P
between 2 students if they shook hands. By the previous problem,
we should have 2|E| = v dv = 111 · 17. But the LHS is even and the RHS is odd, a
contradiction. 

(c) [5 pts] And on a more dull note, how many edges does Kn , the complete graph on n
vertices, have?

P the first part of the problem. Notice that each vertex is joined to n − 1
Solution. Apply
others. 2|E| = v dv = n(n − 1). So |E| = n(n − 1)/2. 

Problem 3. [15 points] Two graphs are isomorphic if they are the same up to a relabeling
of their vertices (see Definition 5.1.3 in the book). A property of a graph is said to be
preserved under isomorphism if whenever G has that property, every graph isomorphic to G
also has that property. For example, the property of having five vertices is preserved under
isomorphism: if G has five vertices then every graph isomorphic to G also has five vertices.

(a) [5 pts] Some properties of a simple graph, G, are described below. Which of these
properties is preserved under isomorphism?

1. G has an even number of vertices.

2. None of the vertices of G is an even integer.
3. G has a vertex of degree 3.
4. G has exactly one vertex of degree 3.
4 Problem Set 4

Solution. 1. It is invariant under isomorphism. There must be an one-to-one and onto

mapping between the vertices of two isomorphic graphs. Therefore, the number of
vertices in the two graphs must be the same. If one graph has even number of vertices,
then the other must have even number of vertices.
2. It is not invariant under isomorphism. We do not really care what the vertices are.
Vertices can be any kind of mathematical objects. All we are interested is that whether
there exists a one-to-one and onto function f mapping from vertices of one graph to
vertices of another with the property that a and b are adjacent in the first graph if and
only if f (a) and f (b) are adjacent in the second graph, for all a and b in the first graph.

So, for example, let G1 be a graph with a single vertex, 1, and G2 be a graph with
a single vertex, 2. Obviously the two graphs are isomorphic, but G2 does not have
vertices which are even integers.
3. It is invariant under isomorphism.
Let G1 , G2 be simple graphs and f : V1 → V2 be an isomorphism between them. Suppose
v ∈ V1 has degree 3; we want to show that there is a vertex of degree 3 in V2 . In fact,
we’ll show that f (v) has degree 3.
Since v has degree 3, there are exactly 3 vertices adjacent to v; say these are v1 , v2 , v3 .
Since f is a bijection, f (v1 ), f (v2 ) and f (v3 ) are all distinct. Since there is an edge
between v and vi in G1 , the definition of isomrphism implies that there is an edge
between f (v) and f (vi ) for i = 1, 2, 3, so the degree of f (v) is at least 3.
We now prove by contradiction that the degree of f (v) is at most 3. Suppose f (v) had
degree > 3. This means there is a vertex w ∈ V2 which is not equal to f (v1 ), f (v2 ),
or f (v3 ), but is also adjacent to f (v). Since, f is a bijection, there is a vertex v4 ∈ V1
such that f (v4 ) = w and v4 6= vi for i = 1, 2, 3. Since w = f (v4 ) is adjacent to f (v),
the definition of isomorphism implies that v4 is adjacent to v, contradicting the fact the
v1 , v2 , v3 were exactly the vertices adjacent to v.
4. It is invariant under isomorphism.
Prove by contradiction: Suppose a graph G1 has exactly one vertex of degree 3 while
another graph G2 does not have exactly one vertex of degree 3. Suppose the two graphs
are isomorphic. If G2 does not have a vertex of degree 3, then from part (c), there is a
contradiction. If G2 has more than one vertices of degree 3, then there must be at least
one vertex in G2 of degree 3 which is mapped to a vertex of degree 6= 3 in G1 . Since two
vertices of different degrees are mapped from G1 to G2 , using the same argument from
part (c), it reaches a contradiction. Therefore, if G1 has exactly one vertex of degree 3,
then G2 must also have exactly one vertex of degree 3.


(b) [10 pts] Determine which among the four graphs pictured in the Figures are isomorphic.
If two of these graphs are isomorphic, describe an isomorphism between them. If they are not,
give a property that is preserved under isomorphism such that one graph has the property,
but the other does not. For at least one of the properties you choose, prove that it is indeed
preserved under isomorphism (you only need prove one of them).
Problem Set 4 5

1 1

6 6
5 8 9 2 5 9 7 2

10 7 10 8

4 3 4 3
(a) G1 (b) G2
1 1
9 2
6
5 9 7 2
8 3
10
10 8
7 4

6 5 4 3
(c) G3 (d) G4

Figure 1: Which graphs are isomorphic?

Solution. G1 and G3 are isomorphic. In particular, the function f : V1 → V3 is an

isomomorphism, where

f (1) = 1 f (2) = 2 f (3) = 3 f (4) = 8 f (5) = 9

f (6) = 10 f (7) = 4 f (8) = 5 f (9) = 6 f (10) = 7

G1 and G4 are not isomorphic to G2 : G2 has a vertex of degree four and neither G1 nor G4
has one.
G1 and G4 are not isomorphic: G4 has a simple cycle of length four and G1 does not.


Problem 4. [15 points] Recall that a coloring of a simple graph is an assignment of a

color to each vertex such that no two adjacent vertices have the same color. A k-coloring
is a coloring that uses at most k colors.
False Claim. Let G be a (simple) graph with maximum degree at most k. If G also has a
vertex of degree less than k, then G is k-colorable.

(a) [5 pts] Give a counterexample to the False Claim when k = 2.

Solution. One node by itself, and a separate triangle (K3 ). The graph has max degree 2,
and a node of degree zero, but is not 2-colorable. 
6 Problem Set 4

(b) [10 pts] Consider the following proof of the False Claim:

Proof. Proof by induction on the number n of vertices:

Induction hypothesis: P (n) is defined to be: Let G be a graph with n vertices and
maximum degree a most k. If G also has a vertex of degree less than k, then G is k-colorable.
Base case: (n=1) G has only one vertex and so is 1-colorable. So P (1) holds.
Inductive step:
We may assume P (n). To prove P (n + 1), let Gn+1 be a graph with n + 1 vertices and
maximum degree at most k. Also, suppose Gn+1 has a vertex, v, of degree less than k. We
need only prove that Gn+1 is k-colorable.
To do this, first remove the vertex v to produce a graph, Gn , with n vertices. Removing v
reduces the degree of all vertices adjacent to v by 1. So in Gn , each of these vertices has
degree less than k. Also the maximum degree of Gn remains at most k. So Gn satisfies the
conditions of the induction hypothesis P (n). We conclude that Gn is k-colorable.
Now a k-coloring of Gn gives a coloring of all the vertices of Gn+1 , except for v. Since v has
degree less than k, there will be fewer than k colors assigned to the nodes adjacent to v. So
among the k possible colors, there will be a color not used to color these adjacent nodes,
and this color can be assigned to v to form a k-coloring of Gn+1 .

Identify the exact sentence where the proof goes wrong.

Solution. “So Gn satisfies the conditions of the induction hypothesis P (n).” The flaw
is that if v has degree 0, then removing v will not reduce the degree of any vertex, and
so there may not be any vertex of degree less than k in Gn , as in the counterexample of
part (a). 

Problem 5. [15 points] Prove or disprove the following claim: for some n ≥ 3 (n boys
and n girls, for a total of 2n people), there exists a set of boys’ and girls’ preferences such
that every dating arrangement is stable.

Solution. The claim is false.

Proof. We will use letters to denote girls and numbers to denoted boys.
There must be some girl A rated worst by at most n − 2 boys. The reason is as follows.
Each boy can rate exactly one girl worst. If each of the n girls was rated worst by at least
n − 1 boys, then there would have to be at least n(n − 1) boys in all. But this is false when
n ≥ 3, because then n(n − 1) exceeds n, the actual number of boys.
Suppose that this girl A is paired with the boy, 1, that she rates worst. Since at most
n − 2 boys rate girl A worst, there is some other boy, 2, that rates a different girl, B, worst.
Suppose that boy 2 is paired with girl B.
Problem Set 4 7

Now girl A and boy 2 form a rogue couple. Girl A prefers every other boy to her date, 1.
Similarly, boy 2 prefers every other girl to his date B. Therefore, A and 2 prefer one another
to their current dates.


Problem 6. [20 points]
Let (s1 , s2 , ..., sn ) be an arbitrarily distributed sequence of the number 1, 2, ..., n − 1, n. For
instance, for n = 5, one arbitrary sequence could be (5, 3, 4, 2, 1).
Define the graph G=(V,E) as follows:

1. V = {v1 , v2 , ..., vn }

2. e = (vi , vj ) ∈ E if either:

(a) j = i + 1, for 1 ≤ i ≤ n − 1
(b) i = sk , and j = sk+1 for 1 ≤ k ≤ n − 1

(a) [10 pts] Prove that this graph is 4-colorable for any (s1 , s2 , . . . , sn ).
Hint: First show that a line graph is 2-colorable. Note that a line graph is defined as follows:
The n-node graph containing n − 1 edges in sequence is known as the line graph Ln .
Solution. First we argue that any line graph is 2-colorable. Consider the line graph Ln
with vertices v1 , v2 , v3 , . . . , vn . Suppose we have two colors A and B. Then color all odd
numbered vertices with color A and all even numbered vertices with color B. Since each
odd vertex is adjacent only to even vertices, and vice versa, this is a valid 2-coloring.
Consider G. G is composed of two—possibly overlapping—line graphs: one line graph
contains the vertices of G in order, while the other line graph of the vertices of G in the
order of our sequence (s1 , . . . , sn ). Pick one of these two graphs to color first using colors
A and B. This will be a temporary coloring. Now color the second line graph with colors
C and D, noting that these are temporary colors as well. Now each vertex will be assigned
two colors, one from the first line graph and one from the second line graph (since both
line graphs contain all vertices). Define four new colors, AC, AD, BC, BD. Color the graph
with AC if one temporary color is A and the other temporary color is C. Color the graph
with AD if one temporary color is A and the other is D. Do the same with colors BC and
BD.
We note that our original temporary colors represent adjacencies in the graph. That is we
note that each vertex has at most 4 adjacent nodes (two from each line graph). If the first
color is A then two of the adjacenct vertices will be colored B, and vice versa. If the second
color is C, then the other two adjacenct vertices will be colored D, and vice versa. So if a
graph has a specific color, such as AC, then it is adjacent only to vertices of color B and
D. Since we color those vertices differently (with one of AB, BC, or BD), then our coloring
does not color two adjacent vertices with the same color. 
8 Problem Set 4

(b) [10 pts] Suppose (s1 , s2 , . . . , sn ) = (1, a1 , 3, a2 , 5, a3 , . . .) where a1 , a2 , . . . is an arbitrary

distributed sequence of the even numbers in 1, . . . , n − 1. Prove that the resulting graph is
2-colorable.

Solution. Color all odd vertices with first color. Now color all the even vertices with
a second color. Note that by problem definition odd vertices are only adjacent to even
vertices and vice versa, hence this is a valid 2-coloring.