6.9 Turán
Turan: Suppose \(G\) is simple graph on \(n\) vertices that does not have a p-clique.
What is the largest number of edges that \(G\) can have?
If \(p=2\), then it is \(0\)
How can we construct a graph that does not have triangle \(p=3\) case
This graph has \(n\cdot m\) edges, this number maximizes when \(|n-m|\leq 1\)
We shift one point in \(n\) to \(m\), then \(n\geq m+2\)
\((n-1)(m-1)=nm-n-m+1\geq nm+1\) since \(n\geq m+2\)
Thus when \(n\geq 3\), there is a graph on \(\begin{cases} \lfloor \frac{n}{2}\rfloor\cdot \lfloor \frac{n}{2}+1\rfloor&\text{if }n\text{ is odd}\\ \frac{n^2}{4}&\text{if }n\text{ is even} \end{cases}\) edges without triangles
General \(p\) case
Complete \((p-1)\)-partite graph that is \(K_{n_1,...,n_{p-1}}\), then \(\#\)edges \(=\sum_{1\leq i<j\leq p-1}n_in_j\)
It maximizes if \(\forall i,j\) we have \(|n_{i}-n_{j}|\leq 1\). (Note: \(K_{n_1,...,n_{p-1}}\) with \(|n_{i}-n_{j}|\leq 1\) are called Toran graphs)
More simple estimation: If \(p-1\) divides the number of vertices \(n\). Take Turan graph with shelves of the size \(\frac{n}{p-1}\)
\(\#\)Edges\(=\left(\frac{n}{p-1}\right)^{2}\frac{(p-1)(p-2)}{2}=\left(1-\frac{1}{p-1}\right) \frac{n^{2}}{2}\)
Theorem(Turan)
If \(G=(V,E)\) is a simple graph on \(\#V=n\) vertices that does not have \(p\)-clique, then \(\#E\leq\left(1-\frac{1}{p-1}\right)\frac{n^{2}}{2}\)
Proof 1(Turan): Induction on \(n\)
Base: \(n<p\) case. We need to check that \(\frac{n(n-1)}{2}\leq\left(1-\frac{1}{p-1}\right)\frac{n^{2}}{2}\), just expand and use \(n<p\)
Inductive step: Suppose the estimate holds true for all \(n'<n\). Take a graph on \(n\) vertices that does not have \(p\)-cliques
Let \(G\) has maximal possible number of edges. Claim: \(G\) has to have a \(p-1\)-clique
Let \(A\) be the \(p-1\)-clique in \(G\). Set \(B:=V\setminus A\) clearly \(\#B<\#V\)
So for the induced graph \(G[B]\) induction hypothesis applied (as \(G[B]\) does not have p-cliques)
\(\#\)edges of \(G[B]\leq \frac{1}{2}(1-\frac{1}{p-1})(n-(p-1))^2\)
And \(A\) is a \(p-1\)-clique, then every vertex from \(B\) is adjacent to at most \(p-2\) vertices of \(A\)
\(\#\)Edges connecting A and B \(\leq(p-2)(n-(p-1))\)
And there are \(\frac{(p-1)(p-2)}{2}\) edges in \(A\)
The total number of edges is \(\leq\frac{(p-1)(p-2)}{2}+(p-2)(n-(p-1))+\frac{1}{2}(1-\frac{1}{p-1})(n-p+1)^{2}= \left(1-\frac{1}{p-1}\right)\frac{n^{2}}{2}\)
Proof 2: (Erdos)
Let \(V=\{v_{1},...,v_{n}\}\) let \(v_m\) be a vertex of maximal degree \(d_m\)
Denote \(S\) be set of neighbors of \(v_m\) and set \(T=V\setminus S\). In particular \(v_{m}\in T\) since \(v_m\) is not a neighborhood of itself by definition
Note that \(G[S]\) does not have \(p-1\) cliques, otherwise we can add \(v_m\) to form a \(p\) clique
Use this picture to construct a new graph \(H\)
Notice: 1. \(H\) still has no p-cliques 2. \(\forall\) vertices \(v_1,...,v_m\), then \(\deg_Gv_i\leq \deg_Hv_i\), then number of edges also increased
Thus among the graphs on \(n\) vertices that do not have \(p\)-cliques there is some of the form of \(H\)
Then we inducts on \(p\)
Base case: \(p=2\)
Induction hypothesis: The graph that maximizes the number of edges for all \(p'<p\) is the Turan graph \(K_{n_1,...,n_{p'-1}}\)
Note that \(G[S]\) does not have \(p-1\) cliques, so inductive hypothesis applies
\(G[S]=K_{n_1,...,n_{p-2}}\) and \(H=K_{n_1,...,n_{p-2},\#T}\) is also a Turan graph
The only thing left to prove: \(\#\) edges in a Turan graph is \(\leq\frac{1}{2}\left(1-\frac{1}{p-1}\right)\frac{n^{2}}{2}\)
Proper vertex colorings
How many colors are enough to color any possible map?
Actually, \(4\) colors are enough for planar graph
For dual graphs: no two adjacent vertices are colored the same
Claim:
For any planar graph \(6\) colors are enough to produce a proper coloring (no two adjacent vertices are colored same)
Proof: Induction on the number of vertices
Base: Surely \(6\) colors are enough to color properly all the planar graphs with \(n\leq 6\) vertices
Inductive step: Take a planar graph with \(n>6\) vertices
Any planar graph has a vertex of deg \(5\) or less, remove this vertex.
By induction, the graph with \(v\) removed has a proper coloring in \(6\) colors
Choose such a coloring, then return \(v\) back to the graph, then \(\deg v\) is at most \(5\), then we will have at least one color to color \(v\)
Thus it is possible
General
Let \(G\) be a simple graph, \(V\) is the set of vertices of \(G\), \(C\) is the set of colors s.t. \(\#C=c\)
\(\chi_G(c)=\#\{f:V\to C:f\text{ is a proper coloring}\}\) and \(\chi_G:c\mapsto \chi_G(c)\) is chromatic function of the graph
\(4\) colorability \(\iff \chi_{G}(4)\neq 0\)
Obviously property: if \(G=G_{1}\sqcup G_{2}\), then \(\chi_{G_1\sqcup G_2}(c)=\chi_{G_1}(c)\cdot \chi_{G_2}(c)\)
Normalization: \(\chi_{\{*\}}(c)=c\)
Proposition: Let \(G\) be simple graph, then 
\(\chi_{G}(c)=\chi_{G\setminus e}(c)-\chi_{G/e}(c)\)
(coloring of vertices of G with no restrictions of colors of vertices incident to e) - #(colorings of vertices of G with the vertices incident to e colored the same)
The both terms on the right hand side have at least one less edge than in the original graph
Corollary
For any graph \(G\), \(\chi_G(c)\) is a polynomial of degree \(\leq \#V\) in \(c\)
