Extremal graph theory

Definition 6..1 (Monotone)  

A property of a graph is monotone if the whole graph has the property when a subgraph does.

Definition 6..2 (Non-trival property)  

A property of a graph is non-trivial if the empty graph does not have the property.

Definition 6..3 (Extremal problem)  

The study of the minimum size of a graph with a monotone, non-trivial property, or the maximum size of a graph without it.

Theorem 6..4 (Condition for a graph to be Hamiltonian)   Let $G$ be a connected graph of order $n \ge 3$. Suppose that for every pair of non-adjacent vertices $a,b$, $d(a)+d(b) \ge k$.

If $k < n$ then $G$ has a path of length $k$. If $k \ge n$ then $G$ is Hamiltonian.

Note that if $k \ge n$ then the degree condition implies that $G$ is connected.

Proof. Suppose that $G$ is not Hamiltonian. Let $P = x_1 \cdots x_l$ be a path of maximal length.

Claim. $G$ has no cycle of length $l$. Proof of claim. Suppose there is a cycle. Obviously if $l = n$ then $G$ is Hamiltonian, contradiction. If $l < n$ then there is a vertex $w$ not in the cycle. $G$ is connected, so we can find a path from the cycle to $w$, giving a path longer than $l$, contradiction.

In particular, $x_1 x_l \notin E(G)$. Now by hypothesis $d(x_1) + d(x_l) \ge k$.

Let $S = \{ 2 \le i \le l : x_1 x_i \in E(G) \}$, $T = \{ 2 \le i \le l : x_{i-1} x_l \in E(G) \}$. If $j \in S \cap T$ then $x_1 x_j x_{j+1} \cdots x_l x_{j-1} x_{j-2} \cdots x_1$ is a cycle of length $l$. So $S \cap T = \emptyset$.

Certainly $l \notin S,T$ and $S \bigcup T \subseteq \{ 1,\cdots, l \}$, so in fact $k \le d(x_1) + d(x_l) = \vert S\vert + \vert T\vert \le l - 1$.

If $k < n$ then we have a path of length $l-1 \ge k$, so a path of length $k$.

If $k = n$ then we have a path of length $n$, which is a contradiction because it must involve $n+1$ vertices. Therefore $G$ is Hamiltonian. $\qedsymbol$

Corollary 6..5 (G.A. Dirac)  

If $\delta(G) \ge \frac{n}{2}$ then $G$ is Hamiltonian.

Theorem 6..6  

Let $G$ be a graph with $n$ vertices and no path of length $k$. Then $e(G) \le (k - 1) \frac{n}{2}$ with equality iff $G$ is a union of copies of $K_k$.

Proof. By induction on $n$.

If $n \le k$ then $e(G) \le {n \choose 2} \le (k - 1) \frac{n}{2}$ with equality iff $G = K_k$.

Consider $n > k$. If $G$ is disconnected apply induction to each component. Otherwise $G$ is connected and $K_k \not \subset G$, or there would be a vertex $w$ that could be joined to a path traversing the $K_k$ to make a path of length $k$.

By theorem 6.4 at least one $v \in V(G)$ has $d(v) \le \frac{k-1}{2}$. By the induction hypothesis $e(G-v) < \frac{k-1}{2}(n-1)$. Therefore $e(G) < \frac{k-1}{2}n$.

$\qedsymbol$