A THEOREM OF TURAN

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₁ blue and m₂ red vertices, m₁+m₂ = n. [m1-m]2 ≤1
• Suppose that m₂ £ m_1.
• If m₂ + 2 £ m_1, then we choose another complete bipartite graph     with m₂ + 1 red vertices and m₁ - 1 blue vertices.
• Then,

            G has m₁m₂ edges

             has (m₁ - 1) (m₂ + 1) edges

            (m₁ - 1) (m₂ + 1) - m₁m₂ = m₁ - m₂ - 1

• Diasumsikan m₂ £ m₁ - 2 Þ m₁ - m₂ - 1 ³ 1
•        has at least one more edge than G ® colorable 2 colors and has n vertices ® m₁ and m₂ 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₁ + n₂ + . . . + 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₁ + m₂ + . . . + 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₁,m₂,…m_k) so

                        A (m₁,m₂,m₃…m_k) = m₁m₂+A(m₁ + m₂, m_3, . . . ,m_k)

·         Suppose that in G any two of these numbers differ by more than 1, m₂ + 2 £ m₁

·         We consider a new graph  K_m1^-1_,m2⁺¹_,…,mk

·         The number of edges in

A (m₁-1, m₂+1, m₃, …, m_k   = (m₁-1)(m₂+1)+A(m₁+m₂,m₃,…m_k)

Size in      - size G is  (m₁-1)(m₂+1)-m₁m₂ = m₁-m₂-1

·         Since   m₂ + 2 £ m₁

·                                             Þ m₁ - m₂ - 1 ³ 1

·          has at least one more edge than G hence G couldn’t have the max number of edges.

·         Assumption m₂ + 2 £ m₁ 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₁ + n₂ + . . . + 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₁ + n₂ + . . . + 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₁ + n₂ and ê n₁ - n₂ ú £ 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₁ + n₂ and ê n₁ - n₂ ú £ 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₀ be the subgraph induced by the set

• G₀ 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₀ and there exist a (k - 1)-partite graph H₀ 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₀ 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₄

.