EXERCISES: GRAPH THEORY

Margherita Maria Ferrari

1. Prove that there is no graph with seven vertices that is regular of degree 3.

Solution:
Given a graph G = (V, E), the sum of the degrees of the vertices of G is equal to
twice the number of edges; in other words
X
d(v) = 2|E|.
v∈V

In our case we have that all seven vertices have degree equal to 3 and thus we
obtain that X
d(v) = 3 · 7 = 21,
v∈V
which is an odd number. This implies that there is no graph with seven vertices
that is regular of degree 3.
2. G is a connected planar graph of order 24 and it is regular of degree 3. How many
faces are in a planar representation of G?

Solution:
Recall that if G is a connected planar graph with n vertices and m edges, then
the number of faces is p, where n − m + p = 2 (Euler’s formula). In our case
n = 24. To compute the number of edges of G we use the formula
1X
m = |E| = d(v).
2 v∈V

Since G is a regular graph of degree 3 and order 24, we have that

1X 1
m = |E| = d(v) = · 24 · 3 = 36.
2 v∈V 2

Thus p = 2 − n + m = 2 − 24 + 36 = 14.
3. Let n be a positive integer. The n-cube is the graph, denoted Qn , whose vertices
are the 2n possible length-n strings of 0s and 1s. For example, the vertices of Q3
are 000, 001, 010, 011, 100, 101, 110, 111. Two vertices of Qn are adjacent if their
strings differ in exactly one position. For example, in Q4 the vertices 1101 and
1001 are adjacent but 1100 and 1010 are not adjacent.
a) How many edges does Qn have?

b) Prove that Qn is bipartite.

Solution:
The n-cube Qn is the graph whose set of vertices is V = {x1 x2 · · · xn : xi ∈
{0, 1} for all i = 1, 2, . . . , n}. It is esay to see that |V | = 2n . Two vertices
u and v are adjacent if and only if their strings differ in exactly one position.
This means that there exists exactly one index j ∈ {1, 2, . . . , n} such that u =
x1 x2 · · · xj−1 xj xj+1 · · · xn and v = x1 x2 · · · xj−1 xj xj+1 · · · xn , where xj = 1 − xj .

1
 a) To compute the number of edges of Qn we have to determine the value of
the sum of the degrees of vertices of Qn (recall that this sum is equal to
2|E|). Consider a vertex u = x1 x2 · · · xn of Qn . This vertex is adjacent to
the following vertices:
x 1 x2 · · · xn
x 1 x2 · · · xn
..
.
x1 x2 · · · xn
where xj = 1 − xj . This means that u is adjacent to exactly n vertices (i.e.
d(u) = n) and, as a consequence, Qn is a regular graph of degree n. This
implies that the sum of the degrees of the vertices of Qn is equal to 2n · n,
and so
2|E| = 2n · n ⇒ |E| = n · 2n−1 .
b) The graph Qn = (V, E) is bipartite if the vertices of Qn can be partitioned
into two subsets A and B so that each edge of Qn has one vertex in A and
one vertex in B.
Consider the following sets:

A = {x1 x2 · · · xn ∈ V : x1 + x2 + · · · + xn is even};

B = {x1 x2 · · · xn ∈ V : x1 + x2 + · · · + xn is odd}.
Clearly A ∪ B = V and A ∩ B = ∅. It remains to prove that every edge of
Qn joins a vertex in A to a vertex in B.
Let e = uv be an edge of Qn . From the definition of Qn we have that
u = x1 x2 · · · xj−1 xj xj+1 · · · xn and v = x1 x2 · · · xj−1 xj xj+1 · · · xn .
Suppose that xj = 0. Thus xj = 1.
If x1 + · · · + xj−1 + 0 + xj+1 + · · · + xn is even, then x1 + · · · + xj−1 + 1 +
xj+1 + · · · + xn is odd. This means that if u ∈ A then v ∈ B.
If x1 + · · · + xj−1 + 0 + xj+1 + · · · + xn is odd, then x1 + · · · + xj−1 + 1 +
xj+1 + · · · + xn is even. This means that if u ∈ B then v ∈ A.
We can repeat the same argument if xj = 1. This proves that Qn is bipartite.

4. G is a connected graph with 20 edges. Find the maximum number of vertices that
G can have.

Solution:
If G = (V, E) contains a cycle, we can transform G into a new graph with the
same number of edges but with a greater number of vertices using the following
procedure:

1. delete an edge of the cycle;

2. add a new edge that joins a vertex of G to a new vertex.

The graph G0 = (V 0 , E 0 ) obtained in this way is connected with |V 0 | = |V | + 1

and |E 0 | = |E|.
As a consequence, the connected graph G with 20 edges and with the maximum
number of vertices must not contain cycles; in other words G must be a tree. In
this case, if we denote n = |V |, we obtain that n − 1 = |E| = 20, which implies
that n = 21.

2
5. Consider the following bipartite graph G = (X ∪ Y, E). Starting from the given
matching M formed by red edges, construct a complete matching of G.

Solution:
A matching is a subset of the edge set E such that no two edges share a common
vertex. If |X| ≤ |Y | and |M | = |X|, then M is called a complete matching.
Recall that a bipartite graph admits a complete matching if and only if Hall’s
condition is satisfied: |J(A)| ≥ |A| for all A ⊆ X, where J(A) = {y ∈ Y |xy ∈
E for some x ∈ A}. Note that Hall’s condition is satisfied for the given graph.

In our case M is not a complete matching; thus we need to use the same procedure
of the proof of Hall’s theorem to construct a complete matching starting from M .

Consider the selected vertex of X which is unmatched.

It is adjacent to a vertex of Y that is unmatched in M ,

thus we can construct a new matching by adding the dashed edge to M , obtaining
the matching M 0 :

3
 X

It remains one vertex in X that is unmatched:

In this case the selected vertex is adjacent to only one vertex of Y which is already
matched in M 0 :

The blue vertex of X is adjacent to one vertex of Y that is unmatched:

We can see that in the dashed path P the first and last edges are not in M 0 ,
while the middle edge is in M 0 . We construct a new matching M 00 in which the
first and last edges of P are in M 00 , while the middle edge is not in M 00 :

The matching M 00 is a complete matching of G.