Graph Theory

Rajiv Raman

November 17, 2023

Abstract
These notes provide a quick background on graph theory.

1 Introduction
Graphs are ubiquitous in computer science and allied fields. In these notes, we study basic topics
in graph theory. A graph G is a pair of sets (V, E), where V is an arbitrary set, and E ⊆ V × V ,
i.e., E is a subset of the cartesian product of V with itself. E is called the set of edges of the
graph. Note that we have not restricted V in any way. So, V can be finite, countably infinite, or
even uncountably infinite. A graph G is said to be finite if V is finite, and is infinite otherwise.
However, we will focus only on the setting where V is finite, as that is the most common kind of
graphs that we encounter. So, unless stated otherwise, we assume that the graphs in these notes
are finite.
The set E ⊆ V × V . A standard way to represent a graph is by a drawing in the plane. The
vertices are represented by points in the plane with labels, and the edges are drawn by directed
arcs, where for an edge (i, j), we represent it by a directed arc with tail at i and head at j. An
edge (i, i) is called a self-loop, and is drawn by an arc from i to i. Figure 1 shows a graph.

Figure 1: A drawing of a graph.

The graphs we just described are called directed graphs with self-loops and typically in graph
theory we sometimes avoid self-loops. Graphs with directed arcs are also called digraphs. In

1
graph theory, we typically restrict the notion of graphs even further - we assume that the set E is
symmetric and not reflexive. If the relation E is symmetric, if (i, j) ∈ E ⇒ (j, i) ∈ E. Therefore,
we can ignore directions and replace E by a set of unordered pairs, i.e., sets of size 2. If {i, j} is
an edge, then i and j are said to be adjacent. Figure 2 shows an example of a graph. We usually
reserve the term arc for directed edges and use the term edge for the unordered pairs (or undirected
edges).

Figure 2: A drawing of an undirected graph.

Finally, sometimes it is useful in applications to allow E to be a multi-set. Hence, we may have

many arcs or edges between pairs of vertices. Such a graph is called a multi-graph. Figure ??.
shows an example of a multi-graph. We use the term simple graph to distinguish the case that E
is a set and not a multi-set.
To summarize, a graph can have directions on the edges. In this case, these objects are called
digraphs. The graph have an edge or arc from a vertex to itself - a self-loop, or there can be
multiple edges or arcs between the same pair of nodes. These are called multi-graphs. When we
use the term graph in these notes, we assume that the graph is finite, simple, without self-loops
and is undirected.
An alternate view to represent a graph is via a matrix. This is useful in many cases as in many
cases, linear algebraic properties of the matrix can tell us about the combinatorial structure of the
graph. An adjacency matrix A of a graph is a square matrix whose rows and columns are indexed
by V . If |V | = n, then A is an n × n matrix. For an undirected graph,

1, {i, j} ∈ E
A[i, j] =
0, {i, j} 6∈ E
We can similarly, define an adjacency matrix for a directed graph D = (V, A) as follows.

 1, (i, j) ∈ E
A[i, j] = −1, (j, i) ∈ E
0, (i, j) 6∈ E and (j, i) 6∈ E


Figure 3 shows an example of a graph and its adjacency matrix.

2
 a
a b c d
a 0 1 0 1
d b b 1 0 1 1
c 0 1 0 1
d 1 1 1 0
c
Figure 3: A graph and its adjacency matrix

2 Important Graphs and Basic Notions

In this section, we introduce some important classes of graphs that have special names. Recall that
the term graph refers to finite, simple, undirected graphs without self-loops. A graph is a clique if
there this an edge between every pair of vertices in the graph. A clique on n vertices is denoted
Kn . Figure 4 shows

examples of cliques. Note that a clique has the maximum possible number of
n
edges, namely 2 .

K1 K2 K3 K4 K5

Figure 4: The graphs K1 , K2 , . . . , K5

A graph G is a path if the vertices can be linearly ordered v0 , v1 , . . . , vn s.t. the edges are
between vertices {vi , vi+1 }, i = 0, . . . , n − 1. These graphs are denoted Pn . If v0 = vn , we obtain
a cycle. A cycle on n vertices is denoted Cn . Figure 5 shows examples of paths and cycles on n
vertices.
A graph G = (V, E) is bipartite if the vertices in the graph can be partitioned into two disjoint
sets V1 t V2 , i.e., V1 ∪ V2 = V and V1 ∩ V2 = ∅ s.t. there are no edges between two vertices u, v ∈ V1
or between vertices u, v ∈ V2 . A bipartite graph G = (V1 ∪ V2 , E) with bipartition V1 t V2 with
|V1 | = m and |V2 | = n is called a complete bipartite graph if for all u ∈ V1 , v ∈ V2 , {u, v} ∈ E. A
complete bipartite graph is denoted Km,n . Note that Kmn has mn edges. Figure 6 shows examples
of complete bipartite graphs.
For a graph G = (V, E) a path in G between two vertices u, v is a set of distinct vertices
u = u0 , u1 , . . . , uk = v s.t. {ui , ui+1 } is an edge for i = 0, . . . , k − 1. If u = v and all vertices
u1 , . . . , uk−1 are distinct, then such a path is a cycle in G.
A graph G = (V, E) is connected if for all pairs u, v ∈ V , there is a path between u and v in G.
If this is not the case, then G is said to be disconnected. Note that connectivity is an equivalence
relation. A vertex u is connected to itself. If u is connected to v, then v is connected to u, and

3
 P1 P2 P3

C3 C4 C5
Figure 5: The graphs P1 , P2 , P3 and C3 , C4 , C5

... ...

K1,2 K1,n K3,3 Kn,n

Figure 6: The graphs K1,2 , K1,n , K3,3 , Kn,n

finally, if u is connected to v and v is connected to w, then u is connected to w via a path. The

equivalence classes defined by connectivity are called the connected components of G. Figure 7
shows an example of a disconnected graph.

Figure 7: A graph with three connected components.

For a digraph D = (V, A), a path is defined in the natural way. However, connectivity is not a
symmetric relation. For vertices u, v ∈ V , there could be a path from u to v, but it is possible that
there is no path from v to u. Such a digraph is called strongly connected if there is a path between

4
every pair of vertices. Figure 8 shows an example of a strongly connected digraph.

Figure 8: The graph on the left is strongly connected, but the graph on the right is not.

Exercise 1
For a vertex set V of size n, how many graphs can we have? How many digraphs?

Exercise 2
Given a vertex set U of size m and V of size n, how distinct bipartite graphs are there
with vertex set U ∪ V ?

Exercise 3
Let V = {1, . . . , n} be a vertex set of size n. How many distinct graphs can we form that
are paths on n vertices? What about cycles?

For a graph G = (V, E), a subgraph is a graph H = (V 0 , E 0 ) where V 0 ⊆ V and E 0 ⊆ {{u, v} ∈

E : u ∈ V 0 and v ∈ V 0 }. That is, a subgraph is a graph that is obtained as follows: We select
a subset of the vertices of G. Then, among the edges of E between pairs of vertices in V 0 , we
select a subset of the edges. This new graph is called a subgraph. An induced subgraph is a graph
G = (V 0 , E 0 ), where we only select the subset V 0 ⊆ V . The edges E 0 ⊆ E are all edges between
pairs of vertices in E. That is, E 0 = {{u, v} : u ∈ V 0 and v ∈ V 0 }. Figure 9 shows a subgraph and
induced subgraph of a graph.
For a graph G = (V, E), the complement of G is the graph G = (V, E) obtained by making each
pair of non-adjacent vertices adjacent, and adjacent vertices non-adjacent. Note that G is also a
simple graph. Figure 10 shows a graph and its complement.
In a graph G = (V, E), the degree of a vertex v ∈ V , denoted deg(v) is the number of edges
incident on it. That is, deg(v) = |{{u, v} ∈ E|. In a directed graph, we have two notions of degree,
namely the in-degree, the number of arcs entering a vertex, or the number of arcs whose head is
at the vertex, denoted din (v), or d+ (v). The out-degree is the number of arcs leaving a vertex, or
the number of arcs whose tail is at the vertex. This is denoted dout (v) or d− (v). In a multigraph,
we count multiplicity of arcs. That is, if there are two arcs (i, j) in G, then it contributes 2 to the
degree. A self-loop contributes one to the in-degree and one to the out-degree.
We are ready to prove our first lemma about graphs.

5
 Figure 9: The shows a subgraph in red and an induced subgraph in blue.

Figure 10: The shows a graph and its complement.

Lemma 1 (Handshake Lemma). Let G = (V, E) be a graph. Then

X
deg(v) = 2|E|
v∈V

Proof. We can count the edges by adding up the edges incident on each vertex. But, this way, each
edge is counted twice and the result follows.

Exercise 4
Prove that the number of odd degree vertices in a graph must be even.

Exercise 5
Prove that either a graph or its complement is connected.

3 Isomorphism
A basic notion that we see throughout mathematics is isomorphism. The term iso means same
and morphism means a transformation. The term iso for same is also used in natural language.

6
Some such terms you may have encountered are isotopes, isotherm, isolines, etc. Two graphs are
isomorphic if they are same in some sense. More formally, we say that two graphs G1 = (V1 , E1 ) and
G2 = (V2 , E2 ) are isomorphic if there is a bijection φ : V1 → V2 s.t. {u, v} ∈ E1 ⇔ {φ(u), φ(v)} ∈
E2 . That is, there is an edge between two vertices in the graph G1 if and only if there is an edge
between their images in E2 . An isomorphism from a graph G1 to itself is called an automorphism.
Every graph has a trivial automorphism, namely the identity map.
Note that an isomorphism is always a bijection from V1 to V2 . However, not all bijections are
isomorphisms. We want to ensure that the adjacency relation between vertices is preserved.
Given an isomorphism between two graphs, it is easy to check that it is indeed an isomorphism.
However, it is a challenging question whether we can design a fast algorithm to decide if two
input graphs are isomorphic. Consider the set of all graphs on n vertices. Note that isomorphism
is an equivalence relation. We now address the question: How many equivalence classes can we
have if the set of graphs on n vertices related by isomorphism? Alternatively, we can ask: how
many graphs on n vertices are there that are pairwise non-isomorphic? Note that if there are k
equivalence classes, we can have at most k graphs that are pairwise non-isomorphic as each graph
must come from a different equivalence class. It is difficult to obtain an exact answer to this
question. However, we can obtain good upper and lower bounds. We have already seen in the
n
previous section that the number of graphs on n vertices in 2( 2 ) . Therefore, a trivial upper bound
n
on the number of pairwise non-isomorphic graphs is 2( 2 ) .
Consider a fixed graph G on n vertices. We know from the chapter on counting that there
are n! bijections between two sets of size n. Therefore, G must be isomorphic to at most n! other
graphs. Since G was chosen arbitrarily, this implies, each equivalence class has size at most n!.
n n
Since there are 2( 2 ) graphs, the number of pairwise non-isomorphic graphs is at least 2( 2 ) n!. Hence,
n n
the number of non-isomorphic graphs is at least 2( 2 )/n! and at most 2( 2 ) . How far apart are these
bounds? We can get an estimate by taking logs.

n2
   
n n 1
log 2( 2 ) = = 1−
2 2 n

n
2( 2 ) n2 nn
 
1
log = 1− − log n/2
n! 2 n 2
2
 
n 1 n
≥ 1− − n log n −
2 n 2
2
 
n 1 log n 1
= 1− − −
2 n n 2n

Here, we use the simple upper bound that n! ≤ nn /2n/2 . As n → ∞, the lower and upper
n
bounds nearly coincide. Therefore, the number of non-isomorphic graphs is close to 2( 2 ) .

4 Graphic Sequences
Given a graph G = (V, E), we construct an n-dimensional vector of non-decreasing natural numbers
(d1 , . . . , dn ), where di is the degree of vertex i. Here, we order the vertices of G in non-decreasing

7
order of their degree. If such a vector corresponds to a graph, then it is called a graphic sequence.
Given a graph, we can easily construct a graphic sequence. What about the other direction? Given
a vector v = (d1 , . . . , dn ) s.t. for all i < j, di ≤ dj , is v a graphic sequence of some graph? In
this section, we study this question. There are some natural requirements? It is easy to check that
the maximum degree in a graph is at most n − 1. Therefore, dn ≤ n − 1. It is easy to construct
sequences that satisfy this requirement but are not graphic sequences. From the exercises in the
previous section, we know that the number of vertices of odd degree in a graph must be even. This
is another necessary condition for a vector to be a graphic sequence. But, even this is not sufficient.
Try to construct a sequence (d1 , . . . , dn ) such that dn ≤ n − 1 and the number of odd entries is
even, but the sequence is not graphic.
We now obtain a condition for a sequence to be graphic.

Theorem 1
Let v = (d1 , . . . , dn ) be a sequence of natural numbers s.t. for i < j, di ≤ dj . Let
v0 = (d01 , . . . , d0n−1 ) be the sequence defined as follows:

di , i < n − dn
d0i =
di − 1, i ≥ n − dn

Then v is a graphic sequence if and only if v0 is a graphic sequence.

Proof. One direction is easy. Suppose v0 is a graphic sequence. There is a graph G0 whose degree
sequence is equal to v0 . Since ee obtain v by adding 1 to the last dn entries and appending dn to
v, the graph G obtained by adding a vertex vn and connecting it to the last dn vertices in v0 has
degree sequence v. Therefore, v is graphic.
To show the other direction requires some work. Suppose v is graphic. There is a graph G
whose degree sequence is v. However, the vertex vn with degree dn may not be adjacent to the
last dn vertices in v. Therefore, deleting G does not necessarily yield the graphic sequence v0 .
In order to show that v0 is graphic, we proceed as follows. Let Gv denote the set of all graphs
whose degree sequence is v. In this set, we will show that there is one nice graph, whose maximum
degree vertex is adjacent to the dn vertices of highest degree. To that end, let us order the graphs
in Gv as follows: For a graph G ∈ Gv , let τ (j) be the highest index of a vertex in its degree
sequence such that vn is not adjacent to vj . That is, vn is adjacent to vn−1 , . . . , vj+1 . For two
graphs G1 , G2 ∈ Gv , G1 ≤ G2 if τ (G1 ) ≤ τ (G2 ). Let G the graph in Gv that is minimal in this
order. Now, we analyze the structure of G. Consider the degree sequence of G. Let j be the highest
index in the degree sequence of G s.t. vn is not adjacent to vj . If j ≤ dn , then vn is adjacent to
dn vertices with highest index in its degree sequence. Deleting vn therefore results in a graph G0
whose degree sequence is v0 . So suppose j > dn . This implies, vn is adjacent to a vertex vi that
appears before j in the degree sequence. Now, di ≤ dj , and vi is adjacent to vn . Therefore, there
is a vertex vk , s.t. dk < dj and vk is adjacent to vj but not vi . Consider the graph G0 obtained by
adding the edges {vn , vj } and {vi , vk }, and removing the edges {vi , vn } and {vj , vk }. The degree
sequence remains unchanged, but in G0 , the highest index of a non-adjacent vertex in the degree
sequence is smaller than j, contradicting the choice of G. Figure 11 shows the argument used in
this proof.

8
 v1 v2 v3 vk vi vj vn

Figure 11: The shows an illustration of the proof of Theorem 1.

Exercise 6
Where was the assumption d1 ≤ d2 ≤ . . . ≤ dn used in the proof? Show that the
statement is not true if we omit this assumption.

Exercise 7
Find two non-isomorphic graphs with the smallest number of vertices with the same
degree sequence.

Exercise 8
Let G be a graph with 9 vertices, each of degree 5 or 6. Prove that it has at least 5
vertices of degree 6 or 6 vertices of degree 5.

Exercise 9
Decide for which n ≥ 2 there exist graphs whose vector consists of n distinct numbers.
For which n are there are graphs whose vectors have n − 1 distinct numbers?

Exercise 10
(*) Prove that (d1 , . . . , dn ) is a graphic sequence if and only if
Pn
1. j=1 di ≡ 0 mod 2, and
Pk Pn
2. j=1 di ≤ k(k − 1) + i=k+1 min(di , k) for all 1 ≤ k ≤ n.

9
5 Euler Tours

6 Trees

7 Planar Graphs
At the start of this chapter we said that graphs are visualized by drawing them in the plane. The
vertices are represented by points and edges by continuous curves between points. However, if the
graph is complicated, the edges cross each other and makes visualization difficult. The class of
graphs that can be drawn in the plane with their edges begin internally disjoint are called planar
graphs. In this section, we study planar graphs and their properties.
Let us start with the notion of drawing formally, and before we do that we want to introduce
the notion of an arc. An arc α is the image of an injective map from the closed interval [0, 1] to
R2 . That is α = γ([0, 1]), where γ : [0, 1] → R2 is a continuous, injective function. The fact that
the function is injective implies that no two points of [0, 1] map to the same point in R2 . In other
words, the curve does not cross itself. Continuity of course, means what you think it means - one
can draw the arc from one end to the other without lifting the pen off of the paper. The points
γ(0) and γ(1) are called the end-points of the arc.

Definition 1 (Drawing)
By a drawing of a graph G = (V, E) we mean an assignment as follows: Let f : V → R2
be an injective function. For each edge e = {u, v}, assign an arc α(e) with end-points u
and v. Further, we assume that no point f (v) lies in the interior of any arc α(e).

A graph together with its drawing is called a topologoical graph. If the arcs are pairwise
internally disjoint, i.e., they do not share any vertices other than their end-points then the drawing
is called planar. A graph is planar if it admits a planar drawing. A planar graph along with its
topological drawing is called a plane graph. Figure ?? shows two different drawings of the same
plane graph.
A set R ⊆ R2 is connected, or path-connected if any two points in R have an arc that is
contained entirely in R. Let G = (V, E) be a plane graph. Removing the points corresponding
to the vertices, and the arcs corresponding to the edges, the plane R2 breaks into disjoint path-
connected sets. Each path-connected component is called a face of the drawing. Since G is finite,
there must be an unbounded face. All other faces are called bounded faces. Note that these are
notions specific to a plane drawing and not to the planar graph itself - which may have many
different drawings, and a different set of faces in each drawing.
Another way to view planar graphs that is particularly appealing is the drawing of planar
graphs on a sphere. In this case, we don’t have to deal with one face being unbounded - all faces
are bounded. To see that any planar graph can be drawn on a sphere, and that for any drawing of
a finite graph on a sphere, we can obtain a plane embedding, we rely on a stereographic projection.
Figure ?? shows an example of a stereographic projection.
We need not restrict our attention to drawing graphs in the plane. We can consider drawing
graphs on other surfaces. For example, we can define drawings of graphs on a torus, or even a
Möbius strip or other more complicated surfaces. Figure ?? shows examples of some surfaces.

10
Graphs can be classified according to the surfaces on which they can be drawn. Again note that
by drawing on a surface, we mean that the vertices and edges are mapped injectively to points and
arcs on the surface, and such that the arcs are pairwise internally disjoint.
We will see that the graph K5 cannot be drawn in the plane, but we can obtain a drawing of
K5 on a torus. A sphere with g handles is said to have genus g. It is easy to see that any graph can
be drawn on a surface with sufficiently large genus - by making a handle for an edge that crosses
other edges. The smallest genus of a surface on which a graph can be drawn is called the genus of
the graph.

7.1 Cycles in planar graphs

A basic result we need while dealing with planar graphs is the infamous Jordan curve theorem,
whose statement is intuitively obvious, but whose proof is not! A jordan curve is a closed curve
without self-intersections. That is, it is an image of a function φ : [0, 1] → R2 that is injective when
restricted to (0, 1), and φ(0) = φ(1).

Theorem 2 (Jordan curve theorem)

Any jordan curve c divides the plane into exactly two path-connected components - the
interior of c and the exterior of c.

Figure 12: A jordan curve and a point in its interior and a point in its exterior

Assuming the Jordan curve theorem, we can prove that some graphs are non-planar.

Theorem 3
K5 is non-planar.

11
Proof. We prove by contradiction. Let b1 , . . . , b5 be the five points corresponding to the vertices
of K5 in some drawing. The arc connected bi and bj will be denoted α(i, j). Since the vertices
corresponding to points b1 , b2 and b3 form a cycle in K5 , it follows that there are arcs α1 (b1 , b2 ),
α2 (b2 , b3 ) and α3 (b3 , b1 ). The union of the arcs α1 , α2 and α3 is Jordan curve c, and thus breaks
R2 into the interior and exterior. There are 2 choices for each of the points b4 and b5 . Each of
them can be in the interior of c or in the exterior of c. Suppose one of them, say b4 is inside c and
b5 is in the exterior of c. Then arc corresponding to the edge between vertices corresponding to b4
and b5 must cross c, which is impossible in any drawing. Therefore, either both b4 and b5 are in
the interior of c, or they are both in the exterior of c. The cases are symmetric, so suppose they
are in the interior of c.
Since there are arcs α4 (b4 , b1 ), α5 (b4 , b2 ) and α6 (b4 , b3 ), it follows that we obtain three additional
Jordan curves c1 , c2 and c3 , where c1 is defined by α4 , α5 and α1 , and so on. Now, b5 is in the
interior of one of the Jordan curves c1 , c2 or c3 . Whichever Jordan curve ci , b5 is in, one of the
points b1 , b2 or b3 is in the exterior of the curve. This implies the arc corresponding to this edge
must cross another arc in its interior. Therefore, there is no such drawing.

For a planar graph G, if e1 , . . . , ek are edges in a cycle, then then the arcs α(e1 ), . . . , α(ek )
form a Jordan curve c in any drawing of G. By the Jordan curve theorem, each face of G either
lies inside c, or outside c. We call this Jordan curve a cycle too. Thus a cycle may refer to a
graph-theoretic cycle, or the Jordan curve in the drawing. For some topological graphs, each face
is the interior or exterior of some cycle in G. But, this is not always true. For example a tree is a
planar graph, and there is only one face.
We show that if we exclude planar graphs that are not 2-connected, then the property above is
satisfied. We already know when a graph is connected. 2-connectivity is a stronger notion. We say
that a graph is 2-connected if removing any vertex leaves the graph connected. For example, if G
were a cycle, then removing a vertex, we still have a path between any pair of vertices.

Theorem 4
A graph is 2-connected if and only if it can be obtained by starting with a triangle and
applying a sequence of edge-subdivisions and edge-additions.

Theorem 5
Let G be a 2-connected planar graph. Then, every face in any planar drawing of G is a
region of some cycle in G.

Proof.

Proof. We prove by induction on n. If G is a triangle, then we are done. The statement follows
from the Jordan curve theorem. Let G = (V, E) be a connected topological planar graph with
at least 4 vertices. Then, by Proposition ?? there is either an edge e ∈ E(G) s.t. G \ {e} is
2-connected, or there are a 2-connected graph G0 = (V 0 , E 0 ) and an edge e ∈ E 0 s.t. G = G%e,
where G%e is the edge-subdivision of G. Since G is topological planar, so is G0 . Each face of G0 is
a region of some cycle.

12
 Consider the case G0 = G − e, where e = {u, v}. The vertices u and v are connected by an arc
α(e). Hence, they lie on a face F of G0 . If F 0 denotes the face bounding α(e), then adding α(e)
divides F into two faces f1 and f2 . The faces F1 and F2 are faces bound by cycles. Hence, the
faces are bound by cycles.
If G0 = G%e, then, each face of G0 is a region of some cycle. Then, G has the same property.
This follows immediately from edge-subdivision.

7.2 A combinatorial Characterization of Planar graphs

Theorem 6
A graph is planar if and only if it has no subgraph isomorphic to a subdivision of K3,3
or K5 .

We will not prove this theorem. But, remarkably, this gives us a combinatorial characterization of
planar graphs without any appeal to drawings.

7.3 Euler’s formula

Theorem 7
For any drawing of a connected planar graph G = (V, E), |V | − |E| + |F | = 2.

Proof. We prove by induction on the number of edges of G. If |E| = ∅, then |V | = 1 and |F | = 1,

and the formula holds. So suppose |E| ≥ 1. We distinguish two cases: If G is a tree, then we
have shown that |V | = |E| + 1, and |F | = 1. Therefore, the formula holds. We therefore only
need to consider planar graphs that contain cycles. Let e ∈ E s.t. e is contained in a cycle.
Then, G0 = G − e is connected and planar. Therefore, |V (G0 )| − |E(G0 )| + |F (G0 )| = 2. Adding
e back increases the number of edges by 1 and the number of faces by 1. Therefore, we obtain
|V (G)| − |E(G0 )| − 1 + |F (G0 )| + 1 = 2.

Theorem 8
A planar graph with at least 3 vertices has at most 3n − 6 edges. Equality holds for any
maximal planar graph.

Proof. If G is not maximal, we can keep adding additional edges until it becomes maximal. In a
maximal planar graph, all faces including the outer face must be triangles. If G is disconnected,
we can connect them by adding an edge. If G is connected but not 2-connected, it has some vertex
v whose removal disconnects the graph creating components V1 , . . . , Vk , k ≥ 2. Choose two edges
e, e0 connecting v to distinct components Vi and Vj s.t. e, e0 are drawn next to each other. Hence,
in a maximal planar graph with at least 3 vertices is 2-connected. Hence, each face is bounded by
a cycle. If a bounding face contains at least 4 vertices, we can add a diagonal.

13
 Therefore, 3|F | = 2|E|. Thus, from Euler’s formula we have

|V | − |E| + |F | = 2
2
|V | − |E| + |E| = 2
3
1
|V | − |E| = 2
3
|E| = 3|V | − 6

Exercise 11
Show that a planar bipartite graph has at most 2n − 4 edges.

7.4 Platonic Solids

A platonic solid, or a regular polytope is a three-dimensional bounded, convex polyhedron with a
finite number of faces, all of whose faces are congruent regular polygons, and such that at each
vertex of the polytope an equal number of polygons meet. The ancient Greeks were fascinated with
the highly symmetric nature of regular polytopes and Kepler even suggested that between the six
planets - Mercury, Venus, Earth, Mars, Juipter and Saturn there lie regular polytopes. A possible
reason why Kepler suggested this is that there are only 5 platonic solids in three dimensions. That’s
it. In this section, we will prove this result. Before we do that however, let us list the platonic
solids. Some may be familiar to you, but the others may not. Corresponding to each platonic solid,
we can associate a planar graph - imagine the edges of the polytope made of an elastic material.
Imagine blowing a balloon that lies inside the polytope. The vertices and edges of the polytope
form a graph embedded in the sphere. As we saw earlier, a planar graph can be equivalently been
seen as embedded in the plane or on the sphere. The platonic solids and their corresponding graphs
are shown in Figure ??.

Theorem 9
There are only five platonic solids.

Proof. The planar graph corresponding to each regular polytope has the following properties: each
vertex has the same degree, and each face has the same number of sides. Let m, n and f denote
respectively, the number of edges, vertices and faces in the graph, let d denote the degree of each
vertex and let k denote the number of sides of each face. Since each vertex has equal degree, by
the Handshake Lemma,

X
deg(v) = dn = 2m
v∈V

14
 Since each face has k sides, and each edge lies on two faces, we have

kf = 2m

Plugging in these in Euler’s formula we obtain

2m 2m
n−m+f = −m+
d k
2 2
=m −1+
d k
=2

Dividing both sides by m, we obtain

2 2 2
−1+ = [subtracting 1 and dividing by 2]
d k m
1 1 1 1
+ = +
d k 2 m
Note that RHS is larger than 1/2. Further, if both d and k were at least 4, then 1/d+1/k ≤ 1/2.
Therefore, at least one of them must be at most 3. Hence, min{d, k} = 3. Suppose d = 3. If d ≥ 6,
then,
1 1 1 1 1
+ = + ≤
3 k 3 6 2
Therefore, d ≤ 5. By a symmetric argument, if k = 3, the only allowable values are 3, 4 and 5.
This gives the following possible values as shown in Figure ??, and this in turn implies there are
only 5 platnoic solids.

8 Coloring planar graphs

A coloring of a graph G = (V, E) is a function φ : V → [k], where [k] = {1, . . . , k} such that
φ(u) 6= φ(v) for all {u, v} ∈ E. The smallest k s.t. there exists a coloring is called the chromatic
number of a graph, denoted χ(G). A set U ⊆ V is an independent set, or a stable set if the vertices
in U are pairwise non-adjacent. Note that for i = 1, . . . , k, φ−1 (i) = {u ∈ V : φ(u) = i} forms an
independent set. The study of the chromatic number of a graph constitutes a very active area of
research in graph theory. Figure 13, 14 shows a coloring of C4 and C5 . It is easy to check that
χ(C4 ) = 2, but χ(C5 ) = 3. In general χ(C2k+1 ) = 3 for k ∈ N, and χ(C2k ) = 2. Let us look at
some other examples. Consider the chromatic numbers of the following graphs: K3 , K4 , K5 . Since
each vertex in Kn is adjacent to all other vertices, we have that χ(Kn ) = n. Figure fig:k345 shows
a coloring of K3 , K4 and K5 . A graph is bipartite if the vertices of G can be partitioned into two
disjoint sets X ∪ Y s.t. all vertices in X are pairwise disjoint, and all vertices in Y are pairwise
disjoint. It is easy to check that χ(G) = 2 for G, a bipartite graph. In fact, bipartite graphs are
precisely the class of graphs with chromatic number 2.

15
 Figure 13: Coloring C4

Figure 14: Coloring C5

K3 K4 K5

Figure 15: Coloring K3 , K4 and K5

Theorem 10
A graph G = (X ∪ Y, E) is bipartite if and only if χ(G) = 2.

Proof. If G is bipartite, since the vertices in X and the vertices in Y are both independent sets, we

16
can color X with color 1 and Y with color 2. On the other hand, if G is 2-colorable, let φ : V → [2]
be a 2-coloring. Then,φ−1 (1) and φ−1 (2) forms a partition of V s.t. φ−1 (1) is an independent set,
and φ−1 (2) is an independent set.

It is easy to check that trees are bipartite graphs.

Exercise 12
Let T = (V, E) be a tree, then show that T is a bipartite graph.

Given a graph, how do we obtain a lower bound on the chromatic number of a graph? For a
graph G = (V, E), a set S ⊆ V s.t. all pairs of vertices in S are adjacent is called a clique in G. The
clique number of G, denoted ω(G) is the largest size of a clique in G. Note that if G has a clique
of size k, then the chromatic number of G is at least k as the vertices in the clique require at least
k colors. Note that for k ∈ N, ω(C2k+1 ) = 2, while χ(C2k+1 ) = 3. Therefore, odd cycles provide
an example of a graph where χ(G) > ω(G). But, how much larger can χ(G) can be compared to
ω(G)? It might seem that a large clique is the only obstacle to having a small chromatic number.
However, the following remarkable theorem was proved by Erdös.

Theorem 11 (Erdös)
For any k ∈ N, there exist graphs with ω(G) = 2 and χ(G) ≥ k.

While we won’t see the proof of this theorem, there are explicit constructions of such graphs.
For example, the Mysielski graph provides such an example. Even more remarkably, Erdös and
Fuchs proved the following theorem:

Theorem 12 (Erdös-Fuchs)
For any g, k ∈ N, g ≥ 3, there exist graphs with χ(G) ≥ k and girth(G) ≥ g.

The girth of a graph G is the length of the smallest cycle in G. This is quite remarkable since
if the girth is g, then from any vertex v in the graph, the subgraph induced by the vertices at
distance at most g − 1 from v, the graph is a tree, which is 2-colorable. Even then, there exist
graphs with arbitrarily large chromatic number. So the chromatic number is a rather ill-behaved
function.
Let G = (V, E) be a graph and let ∆ = maxv∈V deg(v). That is, ∆ is the maximum degree of
a vertex in G. For any graph, we can bound its chromatic number in terms of ∆.

Theorem 13
For any graph G = (V, E) with maximum degree ∆,. χ(G) ≤ ∆ + 1.

Proof. Let us order the vertices of G in linear order. Let v1 , . . . , vn be this order. We color the
vertices with colors {1, 2, . . . , ∆ + 1} in this order so that having colored v1 , . . . , vi−1 we color vi
with the smallest available color. It is immediate that the coloring produced is a legal coloring and

17
it uses at most ∆ + 1 colors. The only thing we need to show is that when we arrive at a vertex,
there is an available color. To see this, when we arrive at vertex vi , the only vertices that have
been colored are the vertices v1 , . . . , vi−1 , and among these vertices, vi has at most ∆ neighbors.
Therefore, there is always an available color for vi .

A graph is d-degenerate if there is an ordering v1 , . . . , vn of the vertices of G s.t. each vertex vi

has at most d neighbors in {v1 , . . . , vi−1 }. Note that by the arguments in the proof of the theorem
above, if G is d-degenerate, χ(G) ≤ d + 1. Some graphs may have vertices of large degree and yet
have small degeneracy.

Theorem 14
Any planar graph is 5-degenerate.

Proof.PLet G be a planar graph. We have seen that m ≤ 3n − 6. By the handshake lemma, we

have v∈V deg(v) = 2m ≤ 6n − 12. Thus, m ≤ 6 − 12/m. Since m is an integer, there is a vertex
of degree at most 5. Let vn be this vertex. We remove vn and put it at the end of a list. We repeat
this process in the remaining graph. Let vn−1 be the next vertex of degree ≤ 5 found. We put vn−1
in front of vn and repeat th process with the remaining vertices. Let v1 , . . . , vn be the ordering.
Then, vi has at most 5 neighbors in v1 , . . . , vi−1 for any i.

Corollary 1. Any planar graph can be colored with at most 6 colors.

We now improve this bound.

Theorem 15
Let G = (V, E) be a planar graph. Then, χ(G) ≤ 5.

Proof. If ∆(G) ≤ 4, then χ(G) ≤ 5. Therefore, we can assume that there is a vertex of degree 5.
Let φ be a coloring of G with the smallest number of colors. Suppose φ uses 6 colors. Then, there
is a vertex v of degree 5 s.t. all its neighbors have different colors. Consider a plane embedding
of G. Let a, b, c, d and e be the neighbors of v in cyclic order in the embedding. Without loss
of generality, let the colors of a, b, c, d and e under φ be respectively 1, 2, 3, 4 and 5. Since G is
planar, it does not have K5 as a complete subgraph. Therefore, one of the pairs among a, b, c, d
and e is non-adjcent. Let a and c be non-adjacent. Consider the induced subgraph graph G13 of
vertices colored 1 or 3. Let Va be the set of vertices of G13 in the connected component of a and
let Vc be the connected component of c in G13 . If a 6∈ Vc , then consider the coloring φ0 obtained
by swapping the colors of the vertices in Va - vertices colored 1 are now colored 3, and vertices
colored 3 are colored 1. Note that this is a legal coloring. In φ0 two of v’s neighbors have the same
color and therefore v can be colored with one of 5 colors. So suppose a ∈ Vc . Then, there is a
path P in Va from a to c consisting of vertices colored 1 or 3. Adding the vertex v and the edges
va and vc yields a cycle C, the edges and vertices of which form a Jordan curve. Since a and c
are non-adjacent in G, the cycle C contains at least one of the neighbors of v in its interior, say b
and another in its exterior, say d. Now consider the graph G24 , the induced subgraph of vertices
colored 2 or 4. It follows that Vb and Vd are disconnected components since ay path between them
must go across C, which is impossible. Now the previous argument implies we can obtain a new

18
coloring φ00 swapping colors 2 and 4 so that in φ00 v has 2 neighbors with the same color, and hence
v can be colored with one of 5 colors.

We can improve the 5 to 4. This is the famous 4-color theorem.

Theorem 16 (Appel-Haken)
Every planar graph can be colored with 4 colors.

Unfortunately, this proof is computer-assisted, requiring a check of thousands of cases. The

number of cases has been reduced to less than 700 by Robertson, Seymour and Thomas, and so if
one is extremely patient, it is possible to check the proof by hand.
Surprisingly, the chromatic number of graphs embedded in a surface of higher genus
√ are easier.
For a graph embedded in a surface of genus g, its chromatic number is at most 7+ 1+48g
2 .

19