Topological graph theory

Definition
A graph G is planar if it can be drawn in the plane such that none of its edges cross.
That is G can be drawn on the plane in such a way that it’s edges intersect only at the
end points.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 3 / 48

Topological graph theory
Definition
A graph G is planar if it can be drawn in the plane such that none of its edges cross.
That is G can be drawn on the plane in such a way that it’s edges intersect only at the
end points.

Can we have a planar graph on 7 vertices?

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 3 / 48

Topological graph theory
Definition
A graph G is planar if it can be drawn in the plane such that none of its edges cross.
That is G can be drawn on the plane in such a way that it’s edges intersect only at the
end points.

Can we have a planar graph on 7 vertices?

Can we have a infinite planar graph?

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 3 / 48

Topological graph theory
Definition
A graph G is planar if it can be drawn in the plane such that none of its edges cross.
That is G can be drawn on the plane in such a way that it’s edges intersect only at the
end points.

Can we have a planar graph on 7 vertices?

Can we have a infinite planar graph?

Can we have a planar graph with minimum degree 6?

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 3 / 48

Topological graph theory
Definition
A graph G is planar if it can be drawn in the plane such that none of its edges cross.
That is G can be drawn on the plane in such a way that it’s edges intersect only at the
end points.

Can we have a planar graph on 7 vertices?

Can we have a infinite planar graph?

Can we have a planar graph with minimum degree 6?

Result
Let G be a simple connected planar graph. Then δ(G ) ≤ 5 where δ(G ) is the minimum
degree of a graph.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 3 / 48

Figure: K5 in torus

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 18 / 48

Theorem (Eulers Formula)
If G is a connected plane graph of order n, size m and having r regions (or faces), then
n − m + r = 2.

Faces:
In any planar graph, the edges divide the planes into different regions.
The regions enclosed by the planar graph are called interior faces of the graph.
The region surrounding the planar graph is called the exterior face of the graph.
When we say faces of the graph we mean BOTH the interior and the exterior faces.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 4 / 48

Proof.
Let G is a tree of order n, then m = n − 1 and r = 1. So, n − m + r = 2.
So, assume G is connected which is not tree and the theorem does not hold.
Then there exist a connected plane graph G of smallest size for which the Euler
identity does not hold.
Suppose that G has order n, size m and r regions. Then n − m + r 6= 2.
Since G is not a tree, there is an edge e that is not a bridge implies G − e is
connected plane graph of order n and size m − 1 having r − 1 regions.
Because the size of G − e is less than m, the Euler identity holds for G − e.
So, n − (m − 1) + (r − 1) = 2 which gives a contradiction to n − m + r = 2.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 5 / 48

Theorem
If G is a planar graph of order n ≥ 3 and size m, then m ≤ 3n − 6

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 6 / 48

Theorem
If G is a planar graph of order n ≥ 3 and size m, then m ≤ 3n − 6

Proof.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 6 / 48

Theorem
If G is a planar graph of order n ≥ 3 and size m, then m ≤ 3n − 6

Proof.
Suppose G is connected and G = P3 . Then the inequality holds.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 6 / 48

Theorem
If G is a planar graph of order n ≥ 3 and size m, then m ≤ 3n − 6

Proof.
Suppose G is connected and G = P3 . Then the inequality holds.
So, assume G has at least 3 edges and draw G as a plane graph where G has r
regions R1 , R2 , . . . , Rr .

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 6 / 48

Theorem
If G is a planar graph of order n ≥ 3 and size m, then m ≤ 3n − 6

Proof.
Suppose G is connected and G = P3 . Then the inequality holds.
So, assume G has at least 3 edges and draw G as a plane graph where G has r
regions R1 , R2 , . . . , Rr .
The boundary of each region contains at least 3 edges.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 6 / 48

Theorem
If G is a planar graph of order n ≥ 3 and size m, then m ≤ 3n − 6

Proof.
Suppose G is connected and G = P3 . Then the inequality holds.
So, assume G has at least 3 edges and draw G as a plane graph where G has r
regions R1 , R2 , . . . , Rr .
The boundary of each region contains at least 3 edges.
If mi is the number of edges of Ri for 1 ≤ i ≤ r , then mi ≥ 3.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 6 / 48

Proof.
Let
r
X
M= mi ≥ 3r .
i=1

The number M counts an edge once if the edge is a bridge and counts it twice the
edge is not in bridge. So, M ≤ 2m. Then clearly, 3r ≤ M ≤ 2m and so 3r ≤ 2m
Now, apply Euler Identity then we get
6 = 3n − 3m + 3r ≤ 3n − 3m + 2m = 3n − m. So, m ≤ 3n − 6
If G is disconnected then edges can be added to G to produce a connected plane
graph of order n and size m′ where m′ > m and so m′ ≤ 3n − 6.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 7 / 48

Theorem
Every planar graph contains a vertex of degree 5 or less.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 8 / 48

Theorem
Every planar graph contains a vertex of degree 5 or less.

Proof.
Suppose that G is a graph every vertex of which has degree 6 or more. Let G have order
n and size m. Clearly, n ≥ 7. Then
X
2m = deg (v ) ≥ 6n.
v ∈V (G )

Thus, m ≥ 3n > 3n − 6. By previous theorem, G is planar.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 8 / 48

Complete graph (Kn ):

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 9 / 48

Complete graph (Kn ):

Complete bipartite graph (Km,n ):

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 9 / 48

Complete graph (Kn ):

Complete bipartite graph (Km,n ):

K4 is planar?

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 9 / 48

Complete graph (Kn ):

Complete bipartite graph (Km,n ):

K4 is planar?

K5 is planar?

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 9 / 48

Complete graph (Kn ):

Complete bipartite graph (Km,n ):

K4 is planar?

K5 is planar?

What about K6 ?

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 9 / 48

Theorem
The complete graph K5 is non-planar.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 10 / 48

Theorem
The complete graph K5 is non-planar.

Proof.
The graph K5 has order n = 5 and size m = 10. Since,m = 10 > 9 = 3n − 6 it follows
that K5 is nonplanar.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 10 / 48

Theorem
The graph K3,3 is nonplanar.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem
The graph K3,3 is nonplanar.

Proof.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem
The graph K3,3 is nonplanar.

Proof.
Assume that K3,3 is planar and draw K3,3 as a plane graph.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem
The graph K3,3 is nonplanar.

Proof.
Assume that K3,3 is planar and draw K3,3 as a plane graph.
Since, n = 6 and m = 9.By the Euler Identity n − m + r = 6 − 9 + r = 2 and so
r = 5.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem
The graph K3,3 is nonplanar.

Proof.
Assume that K3,3 is planar and draw K3,3 as a plane graph.
Since, n = 6 and m = 9.By the Euler Identity n − m + r = 6 − 9 + r = 2 and so
r = 5.
Let R1 , R2 , . . . , R5 be the five region and let mi be the number of edges on the
boundary of Ri for 1 ≤ i ≤ 5.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem
The graph K3,3 is nonplanar.

Proof.
Assume that K3,3 is planar and draw K3,3 as a plane graph.
Since, n = 6 and m = 9.By the Euler Identity n − m + r = 6 − 9 + r = 2 and so
r = 5.
Let R1 , R2 , . . . , R5 be the five region and let mi be the number of edges on the
boundary of Ri for 1 ≤ i ≤ 5.
Since, K3,3 has no triangles, mi ≥ 4 for 1 ≤ i ≤ 5 and because K3,3 contains no
bridges, it follows that
5
X
2m = mi ≥ 20
i=1

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem
The graph K3,3 is nonplanar.

Proof.
Assume that K3,3 is planar and draw K3,3 as a plane graph.
Since, n = 6 and m = 9.By the Euler Identity n − m + r = 6 − 9 + r = 2 and so
r = 5.
Let R1 , R2 , . . . , R5 be the five region and let mi be the number of edges on the
boundary of Ri for 1 ≤ i ≤ 5.
Since, K3,3 has no triangles, mi ≥ 4 for 1 ≤ i ≤ 5 and because K3,3 contains no
bridges, it follows that
5
X
2m = mi ≥ 20
i=1

So m ≥ 10 which gives a contradiction to m = 9.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 11 / 48

Theorem (Kuratowski’s Theorem (1930))
A graph G is planar if and only if G does not contain a subdivision/minor of K5 or K3,3 .

A graph H is a minor of G if H is obtained from G by deletion and contraction of edges

and/or deletion of vertices.

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 12 / 48

u1
b

v1 b u2
b b y1
v2
b b y2

b b
w2 x2
b b
w1 x1

(a).The graph G

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 13 / 48

v2 u1 y2
b b b

x2 b b w2

x1 b b w1

b b b
y1 u2 v1

(b). The subdivision of K3,3 that is a subgraph of the graph G

T. Asir (M. K. University) Embedding of Algebraic Graphs March 20-22, 2019 14 / 48