Discrete Mathematics

Some Theorems on Graphs

1 / 37
 Outline

1 Hamilton Cycles

2 Planar Graphs
Theorem (Ore)
Suppose G is a graph with n ≥ 3 vertices such that for every pair of
non-adjacent vertices u and v, we have

deg(u) + deg(v) ≥ n,

then G has a Hamilton cycle.

3 / 37
 Proof of Ore’s Theorem

• Suppose the theorem is not true.

• There exists a graph G with n vertices and the maximum
number of edges satisfying the conditions of Ore’s theorem
but has no Hamilton cycle. Why?
• Since G has the maximum number of edges, the graph
obtained by adding a new edge connecting two non-adjacent
vertices must have a Hamiltonian cycle containing that added
edge. Why?
• Therefore, any two non-adjacent vertices in G can be
connected by a Hamiltonian path.

4 / 37
 Proof (continued)

• Since the complete graph Kn has a Hamiltonian cycle, G ̸= Kn .

• Therefore, there exist two non-adjacent vertices v1 and vn in
G,
• and there exists a Hamiltonian path:

v1 v2 vn−1 vn
...

5 / 37
 Proof (continued)

• Suppose v1 is adjacent to k vertices: vi , vi , · · · , vi and

1 2 k

2 = i1 < i2 < · · · < i k

• Vertex vn cannot be adjacent to any vertex vi −1 (2 ≤ j ≤ k)

j
because otherwise there would exist a Hamiltonian cycle:

v1 v2 vi j −1 vi j vn−1 vn
... ...

6 / 37
 Proof (continued)

v1 v2 vi j −1 vi j vn−1 vn
... ...

• Therefore, vn is not adjacent to at least k vertices

{vi1 −1 , vi2 −1 , . . . , vik −1 }. That is

deg(vn ) ≤ n − 1 − k

• But then

n ≤ deg(v1 ) + deg(vn ) ≤ k + (n − 1 − k) = n − 1 ✗

7 / 37
Theorem (Dirac)
If G is a graph with n ≥ 3 vertices such that the degree of each
vertex is at least n/2, then G has a Hamilton cycle.

Proof.
• For any two non-adjacent vertices u and v, we have

deg(u) + deg(v) ≥ n/2 + n/2 = n

• Therefore, G satisfies the conditions of Ore’s theorem, hence it

has a Hamiltonian cycle.

8 / 37
 Outline

1 Hamilton Cycles

2 Planar Graphs
 There are always many ways to represent a graph. When is it pos
way to represent this graph in a plane without any edges crossing?
Introduction

FIGURE 1 Three Houses and Three Utilities.

10 / 37
Definition
A graph is called planar if it can be drawn on a plane without any
edges crossing each other. Such a drawing is called a planar
representation of the graph.

FIGURE 2 The FIGURE 3 K4 Drawn

FIGURE 2 The FIGURE 3 K4 Drawn
Graph K . with No Crossings.
Graph K4 . 4 with No Crossings.
11 / 37
 Example
10.7 Planar Graphs 719
10.7 Planar Graphs 719

n FIGURE
FIGURE 4 4 The
The FIGURE 55 AAPlanar
FIGURE Planar
Graph Q3 . Representation of Q3 .
Graph Q3 . Representation of Q3 .

12 / 37
 subregions, R21 and R22 , as shown in Figure 7(
develop some general results that can be used to do this.

planar?
Example v

The graph K3,3 : v1 v2 v3

draw K3,3 in the plane with no edges crossing is doomed. We now
presentation of K3,3 , the vertices v1 and v2 must be connected to both
s form a closed curve that splits the plane into two regions, R1 and
a). The vertex v3 is in either R1 or R2 . When v3 is in R2 , the inside
ges between v3 and v4 and between v3 and v5 separate R2 into two v
s shown in Figure 7(b). v4 v5 v6
is not planar because
FIGURE 6 The Graph K3,3 . F
v1 v5 v1 v5

R21
R2 R1 v3 R1
R22

v4 v2 v4 v2

(a) (b)

FIGURE 7 Showing that K Is Nonplanar. 13 / 37

 Proof: First, we specify a planar representati
a sequence of subgraphs G1 , G2 , . . . , Ge =
is done using the following inductive defini
Euler proved Obtain
that everyGn from
planar Gn−1 byofarbitrarily
representation adding an
a graph divides
the plane into the same number of regions.

R4
R2 R6
R3
R1
R5

FIGURE 8 The Regions of the Planar R

14 / 37
Theorem (Euler’s Formula)
Let G be a connected planar graph with e edges and v vertices. Let
r be the number of regions in a planar representation of G. Then

r = e − v + 2.

15 / 37
Example
Consider a connected planar graph with 20 vertices, each of
degree 3. How many regions does a planar representation of this
graph divide the plane into?
• The sum of degrees is 3v = 3 × 20 = 60
• Number of edges e = 30
• According to Euler’s formula

r = e − v + 2 = 30 − 20 + 2 = 12

16 / 37
 Proof of Euler’s Formula

• We prove by induction on the number of regions r.

• If r = 1, then the graph has no cycles. Why?
• Thus, e = v − 1. ✓
• Assume the theorem holds for r > 1.

17 / 37
 Proof of Euler’s Formula

• Since r > 1, the graph has a cycle.

• Suppose {u, v} is an edge of some cycle.
• Thus, {u, v} is the boundary of two regions S and T . Why?
• Removing the edge {u, v} merges the two regions S and T
into one, while the other regions remain unchanged.
• The new graph obtained has e − 1 edges and r − 1 regions.
• By the induction hypothesis:

r −1= e−1−v+2

• We get r = e − v + 2. ✓

18 / 37
 Corollary
If G is a connected planar graph with e edges and v vertices
s
satisfying v ≥ 3, then e ≤ 3v − 6.

c
7 • The degree of a region is the
b d number of edges on its
R1 3
boundary.
a
R2
• The degree of each region
g must be at least 3.
6 e
R3 • What is the sum of the
degrees of all regions?
f

FIGURE 11 The Degrees of Regions.

19 / 37
Proof.
• The sum of the degrees of all regions
X
deg(R) = 2e ≥ 3r
R

Thus, we have 2e/3 ≥ r.

• By Euler’s formula

r = e − v + 2 ≤ 2e/3.

• Conclude e ≤ 3v − 6.

20 / 37
 Exercise
E, we can produce a subgraph of G by removing the edges in E
subgraph has the
• Using the same vertex
previous setshow
corollary, V asthat
G.theItsgraph
edgeK5set is E − E %
is not
planar.

a a

e b b
e

d c c

ocessors. FIGURE 15 A Subgraph of K5 .

21 / 37
Corollary
If G is a connected planar graph, then G has a vertex of degree at
most 5.

Proof.
Use the previous corollary & the Handshaking Lemma.

22 / 37
Corollary
If a connected planar graph has e edges, v vertices where v ≥ 3,
and no cycles of length 3, then e ≤ 2v − 4.

Proof.
• If there are no cycles of length 3, then the degree of each
region is ≥ 4.
• Exercise: Continue proving this corollary.

23 / 37
 R2 , as shown in Figure 7(a). The ver
of the closed curve, the edges betwe
Exercise
subregions, R21 and R22 , as shown in
• Using the previous corollary, prove that the graph K3,3 is not
planar.

v1 v2 v3

v4 v5 v6

FIGURE 6 The Graph K3,3 .

24 / 37
Definition
The length of the shortest cycle in a graph is called the girth of
that graph.

If the graph has no cycles, then the girth of G is defined as ∞.

25 / 37
Theorem (Edge-Vertex Inequality)
In any connected planar graph G = (V, E) with girth g satisfying
3 ≤ g < ∞, we always have
g
|E| ≤ (|V | − 2).
g −2

26 / 37
 Exercise

Use the edge-vertex inequality to prove that K3,3 and K5 are not
planar graphs.

27 / 37
 Proof of the Edge-Vertex Inequality

• Consider G = (V, E) as a connected planar graph with the

smallest girth 3 ≤ g < ∞.
• Let the edge set E = {e1 , e2 , . . . , e t }.
• Consider any planar representation of G with ℓ regions as

{R1 , R2 , . . . , Rℓ }.

• Construct a matrix X = (x i j ) with t rows and ℓ columns as

follows
¨
1 if ei is an edge on the boundary of region R j
xi j =
0 otherwise

28 / 37
Example
R3
e1 e2 R1 R2 R3
e1 1 0 1
R1
e2 1 0 1
e4 e3 0 1 1
e3
e5 e4 1 1 0
R2
e5 1 0 1
e6 0 1 1
e6 e7 e7 0 1 1

• Each row has at most 2 ones. Why?

• Each column has at least g ones. Why?

29 / 37
 Proof (continued)

• Each edge lies on the boundary of at most two regions, so

each row of X has at most two ones.
• The edges on the boundary of each region form a cycle in G,
so each column has at least g ones.
• Let
s := number of ones in X
we get
gℓ ≤ s ≤ 2t.
with ℓ being the number of regions and t being the number of
edges.

30 / 37
 Proof (continued)

Combining with Euler’s formula

ℓ = t − |V | + 2

we get
gℓ = g t − g|V | + 2g ≤ 2t
Therefore
g
t(g − 2) ≤ g(|V | − 2) ⇐⇒ |E| ≤ (|V | − 2)
g −2

We have completed the proof of the edge-vertex inequality.

31 / 37
 Two Homeomorphic Graphs
Definition
• The operation of removing an edge {u, v} and adding a new
vertex w along with two edges {u, w}, {w, v} is called a
elementary subdivision.
• Two graphs are called homeomorphic if they can be obtained
from the same graph by a sequence of elementary
subdivisions. 10.7 Planar Graphs 723

a b a b a b
G1 G2 G3
h
k
f i
j
g g

c d e c d e c d e

FIGURE 12 Homeomorphic Graphs.

Using r = e − v + 2 (Euler’s formula), we obtain 32 / 37

 Theorem (Kuratowski)
A graph is non-planar if and only if it contains a subgraph that is
homeomorphic to K3,3 or K5 .
hs
Example
a b a b a b

i c i c i c
k h d d
e e
f f
g g g
G H K5

FIGURE 13 The Undirected Graph G, a Subgraph H Homeomorphic to K5 , and K5

Kuratowski’s Theorem
33 / 37
 Petersen Graph

10.7 Planar Graphs 725

Example
a

f c
f d f d j
j
e b
j g
a g

i h
e
i h e i h
d c

(a) (b) H (c) K 3,3

FIGURE 14 (a) The Petersen Graph, (b) a Subgraph H Homeomorphic to K3,3 , and (c) K3,3 .

EXAMPLE 9 Is the Petersen graph, shown in Figure 14(a), planar? (The Danish mathematician Julius Petersen
studied this graph in 1891; it is often used to illustrate various theoretical properties of graphs.)

Solution: The subgraph H of the Petersen graph obtained by deleting b and the three edges
that have b as an endpoint, shown in Figure 14(b), is homeomorphic to K3,3 , with vertex sets
34 / 37
Contracting Two Adjacent Vertices

35 / 37
Definition
A minor of a graph G is a graph obtained from G by a finite
sequence of vertex deletions, edge deletions, and edge
contractions.

36 / 37
Theorem (Wagner)
A graph is non-planar if and only if it contains a minor that is K3,3
or K5 .

37 / 37