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$

John Fremlin 2010-02-17