Turán

by math_explorer, Apr 14, 2011, 4:38 AM

"Complement" means given a graph $G$ , taking every pair of vertices and giving them an edge iff they don't have an edge in $G$ , or equivalently taking the complete graph and removing every edge of $G$ . Of course $G$ has to be simple (no loops or multi-edges) or you get negative edges.

Cliques turn into independent sets. Independent sets turn into cliques. ("Independent set" is a fancy term for "bunch of vertices which don't have any edges connecting two of them.)

"(the complement of) Turán's Theorem": if the maximum independent set of a graph $G$ with $n$ vertices has cardinality $m$ , then $G$ has the minimum number of edges iff $G$ is made of $m$ almost-equally-sized-with-a-tolerance-of-1 disconnected complete graphs.

pf. Let $G$ be a mininum-edge-number example. Our proof will proceed in two steps: first, we show that $G$ must be made of a bunch of complete graphs, and second that these complete graphs must be almost-equally sized.

Claim 1: In $G$ , if $x, y$ are adjacent and $y, z$ are adjacent then $x, z$ are adjacent.

$[asy] unitsize(.4cm); pair px=(-3, -2); pair py=(0, 0); pair pz=(3, -2); draw(px--py, linewidth(1)); draw(py--pz, linewidth(1)); draw(px--pz, linewidth(1)+dashed+red); label("?", (0, -2), S); label("$x$", px, N); label("$y$", py, N); label("$z$", pz, N); [/asy]$

Suppose otherwise. $x, z$ are of course symmetric. Split into cases based on how their degrees compare.
(note: we don't always have that the neighbor sets of $x, y$ are disjoint, as they are in the diagrams. But that just means removing an edge and adding it back; the counting still works.)

Case I

$[asy] unitsize(.4cm); pair px=(-3, -2); pair py=(0, 0); pair pz=(6, -6); pair px1=(-6, -7); pair px2=(-3, -7); pair px3=(0, -7); draw(px--py, linewidth(1)); draw(py--pz, linewidth(1)+dashed); draw(px--px1, linewidth(1)); draw(px--px2, linewidth(1)); draw(px--px3, linewidth(1)); draw(py--px1, linewidth(1)+blue); draw(py--px2, linewidth(1)+blue); draw(py--px3, linewidth(1)+blue); draw(py--(2, -6), linewidth(1)+dashed); draw(py--(3, -6), linewidth(1)+dashed); draw(py--(4, -6), linewidth(1)+dashed); draw(py--(5, -6), linewidth(1)+dashed); label("$x$", px, N); label("$y$", py, N); label("$z$", pz, NE); label("$x$'s neighbors$\setminus \{y\}$", px2, S); label("$y$'s neighbors$\setminus \{x\}$", (5, -6), S); [/asy]$

Suppose $\deg y > \deg x$ . Now, if we take $y$ , delete all its edges except the one with $x$ , and connect it to all of $x$ 's neighbors except itself, we will have decreased the number of edges of $G$ (we've replaced $\deg y - 1$ edges with $\deg x - 1$ edges). But any independent set that the new $G$ has, the old $G$ has as well: $x$ and $y$ , being connected, can't both appear, so simply replace $y$ by $x$ if present. Contradiction! Same goes for $\deg y > \deg z$ .

Case II

$[asy] unitsize(.4cm); pair px=(-3, -2); pair py=(0, 0); pair pz=(3, -2); pair py1=(-2, -7); pair py2=(0, -7); pair py3=(2, -7); draw(px--py, linewidth(1)); draw(py--pz, linewidth(1)); draw(px--pz, linewidth(1)+blue); draw(py--py1, linewidth(1)); draw(py--py2, linewidth(1)); draw(py--py3, linewidth(1)); draw(px--(-5,-6), linewidth(1)+dashed); draw(px--(-7,-6), linewidth(1)+dashed); draw(px--(-9,-6), linewidth(1)+dashed); draw(px--(-11,-6), linewidth(1)+dashed); draw(pz--(5,-6), linewidth(1)+dashed); draw(pz--(7,-6), linewidth(1)+dashed); draw(pz--(9,-6), linewidth(1)+dashed); draw(pz--(11,-6), linewidth(1)+dashed); draw(px--py1, linewidth(1)+blue); draw(px--py2, linewidth(1)+blue); draw(px--py3, linewidth(1)+blue); draw(pz--py1, linewidth(1)+blue); draw(pz--py2, linewidth(1)+blue); draw(pz--py3, linewidth(1)+blue); label("$x$", px, N); label("$y$", py, N); label("$z$", pz, N); label("$y$'s neighbors$\setminus\{x,z\}$", py2, S); label("$z$'s neighbors$\setminus\{y\}$", (8, -6), S); label("$x$'s neighbors$\setminus\{y\}$", (-8, -6), S); [/asy]$

Suppose $\deg y \leq \deg x$ and $\deg y \leq \deg z$ . Now, take $x$ and $z$ , delete all their edges except the ones with $y$ , and connect them to all of $y$ 's neighbors. This replaces $(\deg x - 1) + (\deg z - 1)$ edges with $(\deg y - 1) + (\deg y - 1) - 1$ edges (the last $-1$ because $xz$ is overcounted), and hence also decreases the number of edges of $G$ . Furthermore $x, y, z$ are now all connected. But, again, any independent set in the new $G$ is in the old $G$ ; simply replace whichever of $x, y, z$ appears by $y$ . Contradiction!

Now, is-adjacent-to is transitive, so two vertices in the same connected set are adjacent, meaning that $G$ is a bunch of disconnected complete graphs.

To see that the complete graphs have minimum edge count when almost equal in size, use partial adjustment; if two complete graphs have $a$ and $b$ vertices and $a - b \geq 2$ , then replace them by complete graphs $a-1$ and $b+1$ .

This completes the proof.