A THEOREM
OF TURAN

Introduction

- Extremal
problem are problem that ask what is the largest or smallest graph with a
speficied property.
- “the
largest” ®
the graph with the most edges, given the number of vertices.
- The number
of vertices in G : Order of G
- The number
of edges in G : Size of G
- Induced
Subgraph of a graph G is a subgraph of G obtained by taking a subset W of
the vertices of G together with every edge of G that has both endpoints in
W.

Problem 1

Find a largest graph G with n vertices and chromatic
number two

Solution :

- Since G has
chromatic number two, the vertices are colored by two colors, red and
blue.
- If there is
a red vertex that is not adjacent to a blue vertex, we can add this edge
and increase the number of edges .
- So blue
vertex is adjacent to every red vertex Þ
complete bipartite graph.

Find a largest graph G with n vertices and chromatic
number two

Solution :

- Suppose
there are m
_{1}blue and m_{2}red vertices, m_{1}+m_{2}= n. [m1-m]2 ≤1 - Suppose
that m
_{2}£ m_{1.} - If m
_{2}+ 2 £ m_{1,}then we choose another complete bipartite graph with m_{2}+ 1 red vertices and m_{1}- 1_{ }blue vertices. - Then,

G has m

_{1}m_{2}edges_{ }
has (m

_{1}- 1) (m_{2}+ 1) edges
(m

_{1}- 1) (m_{2}+ 1) - m_{1}m_{2}= m_{1}- m_{2}- 1- Diasumsikan
m
_{2}£ m_{1}- 2 Þ m_{1}- m_{2}- 1 ³ 1 - has at least one more edge than G ®
colorable 2 colors and has n vertices ®
m
_{1}and m_{2}differ by at most one.

Find a largest graph G with n vertices and chromatic
number two

Solution :

- There is a
way to write the result by using Gauss’ symbol for the greatest integer
function.

ëxû
= the greatest integer £ x

Using this notation, the graph G that is the solution to
our problem is the graph with

Find a largest graph G with n vertices and chromatic
number k

- Suppose
that n is some positive integer and we wish to have n = n
_{1}+ n_{2}+ . . . + n_{k}, n_{i}as close in value as possible. - n divisible
by k ®
n = k, n is not divisible by k, then any two of them will differ by no
more than one.
- ê
n
_{i}+ n_{j}ú £ 1, for all i and j

For
example :

n =15, k = 4

Solution

15 = 3 + 4 + 4 + 4

Problem 2

PROBLEM : Find the largest graph G with n vertices and chromatic number k

SOLUTION :

·
Since G is
k-chromatic, the vertices of G can be colored with k colors.

·
m

_{i}be the number of vertices colored with color i = 1,2, . . . , k
Þ n = m

_{1}+ m_{2}+ . . . + m_{k}
Þ G complete
k-partite graph K

_{m1,m2,…,mk}
·
Denote the
number of edges k-partite graph K

_{m1,m2,…,mk}
by A (m

_{1},m_{2},…m_{k}) so
A
(m

_{1},m_{2},m_{3}…m_{k}) = m_{1}m_{2}+A(m_{1 }+ m_{2}, m_{3, }. . . ,m_{k})
·
Suppose that
in G any two of these numbers differ by more than 1, m

_{2}+ 2 £ m_{1}
·
We consider a
new graph K

_{m1}^{-1}_{,m2}^{+1}_{,…,mk}
·
The number of
edges in

A (m

_{1}-1, m_{2}+1, m_{3}, …, m_{k }= (m_{1}-1)(m_{2}+1)+A(m_{1}+m_{2},m_{3},…m_{k})
Size in - size G is (m

_{1}-1)(m_{2}+1)-m_{1}m_{2}= m_{1}-m_{2}-1
·
Since m

_{2}+ 2 £ m_{1}
·
Þ m

_{1}- m_{2}- 1 ³ 1
·
has at least one more edge than G
hence G couldn’t have the max number of edges.

·
Assumption m

_{2}+ 2 £ m_{1}leads to contradiction ® any two of the numbers m_{i }and m_{j}differ by at most one. Proved !
THEOREM 4.1.1

“The largest graph with n vertices and chromatic
number k is a complete k-partite graph

with n = n

_{1}+ n_{2}+ . . . + n_{k}and ê n_{i}- n_{j}ú £ 1 ”
Find the largest graph G with n vertices and
chromatic number k

THEOREM 4.1.2 (TURAN) : The largest graph with n vertices that contains no subgraph isomorphic to
K

_{k+1}is a complete k-partite graph K_{m1,m2,…,mk}with n = n_{1}+ n_{2}+ . . . + n_{k}and ê n_{i}- n_{j}ú £ 1
Proof :

- The conclusion of Theorem 4.1.2 = Theorem 4.1.1
- The assumption of Theorem 4.1.1 implies the
assumption in Theorem 4.1.2, but not conversely.
- Certainly no graph with chromatic number k
contains a subgraph isomorphic to K
_{k+1.}

Theorem 4.1.2* : The largest graph with n vertices
that contains no triangle is a complete bipartite graph K

_{n1,n2}with n = n_{1}+ n_{2}and ê n_{1}- n_{2}ú £ 1
Proof :

- Let be a graph with n vertices that doesn’t contain triangle.
- Let V be the vertex set of G.
- Choose a vertex x of G so deg
_{G}(x) is maximal. - Consider the set W of vertices of G that adjacent to x.
- G would contain a triangle.
- Define a new graph H with the same set of vertices V as G.
- Let W be the same subset of V as above
- Every vertex in V-W is adjacent to every vertex in W in H.
- H is complete bipartite graph.
- If z is a vertex in V-W, then deg
_{H}(z) = deg_{H}(x) = deg_{G}(x) ³ deg_{G}(z) - x to be a vertex of maximal degree in G.
- Suppose that the number of vertices in W is w.
- Then if z is a vertex in W, deg
_{H}(z) = n - w ³ deg_{G}(z), So G would contain a triangle. - Thus we have found a new graph H such that degG(z) £ degH(z).
- The total number of edges in H must be at least the number of edges
in G.
- H is a complete bipartite graph.
- Based on theorem 4.1.1, the largest complete bipartite graph with n
vertices is K
_{n1,n2}with n = n_{1}+ n_{2}and ê n_{1}- n_{2}ú £ 1.

LEMMA 4.1.3 : If G is a graph on n vertices that contains no Kk+1 then
there is a k-partite graph H with the same vertex set as G such that degG(z) £ degH(z) for
every vertex of G.

PROOF :

- Suppose
that the lemma is true for all values less than k

Suppose that G is a
graph with n vertices not containing K

_{k+1}.- Let V be
the vertex set of G

Let x be a vertex of G
with deg

_{G}(x) maximal.
Let W be the set of
vertices adjacent to x in G.

Let G

_{0 }be the subgraph induced by the set- G
_{0}can’t contain a subgraph isomorphic to K_{k } - Otherwise
G would contain a subgraph isomorphic to K
_{k+1}since x is adjacent to all the vertices of W. - Thus the
lemma holds for G
_{0}and there exist a (k - 1)-partite graph H_{0}such that deg_{Go}(z) £ deg_{Ho}(z) for every vertex z in W. - Take the
vertices in V - W and connect each of them to every vertex H
_{0}to form a new graph H

PROOF LEMMA 4.1.3 :

For every vertex z in V - W we have

deg

_{G}(z) £ deg_{G}(x),
deg

_{G}(x) = deg_{H}(x) = deg_{H }(z), . . . deg_{G}(x) maximal
Thus for every vertex z in V - W

deg

_{G}(z) £ deg_{H}(z).
Let z be a vertex in W and w be the number of
vertices in W. So

deg

_{G}(z) £ deg_{G}(z) + n - w,
since z can be adjacent to at most n - w of the
vertices in V - W in G. Also,

deg

_{G}(z) + n - w £ deg_{G}(z) + n - w
by the induction hypothesis. Finally

deg

_{Ho}(z) + n - w = deg_{H}(z)
deg

_{G }(z) £ deg_{H}(z)
Since the above inequality holds for all z in V, the
lemma is proved.

For every vertex z in V - W we have

deg

_{G}(z) £ deg_{G}(x),
deg

_{G}(x) = deg_{H}(x) = deg_{H }(z), . . . deg_{G}(x) maximal
Thus for every vertex z in V - W

deg

_{G}(z) £ deg_{H}(z).
Let z be a vertex in W and w be the number of
vertices in W. So

deg

_{G}(z) £ deg_{G}(z) + n - w,
since z can be adjacent to at most n - w of the
vertices in V - W in G. Also,

deg

_{G}(z) + n - w £ deg_{G}(z) + n - w
by the induction hypothesis. Finally

deg

_{Ho}(z) + n - w = deg_{H}(z)
deg

_{G }(z) £ deg_{H}(z)
Since the above inequality holds for all z in V, the
lemma is proved.

NOTES :

Lemma 4.1.3
shows that if G is a graph with n vertices that doesn’t contain a subgraph
isomorphic to Kk+1, then G can be replaced by a k-partite graph without
decreasing the number of edges. The largest k-partite graph with n vertices is
the complete k-partite graph.

Turan Graph

·
If n and k
given, tis graph is called the

*Turan graph T*_{n,k }
The Turan Graph T

_{15,4 }
·
The octahedron
graph is so also the graph T

_{6,3}the largest graph on six vertices that contains no K_{4 }
.

_{ }