131.4 Connectivity13312:1Proof. Put := e(G) (≥ 2k), and consider the subgraphs G' C G suchthatIG'I≥2k and IIG'l >(IG'I-k).(*)Such graphs G' exist since G is one; let H be one of smallest order.HNo graph G' as in (*) can have order exactly 2k, since this wouldimply that G' > k ≥ 2k? > (IC'l). The minimality of H thereforeimplies that (H) > : otherwise we could delete a vertex of degree atmost and obtain a graph G' C H still satisfying (*). In particular, wehave [H] ≥. Dividing the inequality of |HIl >|H] -k from (*) by[H| therefore yields e(H) > - k, as desiredIt remains to show that H is (k + 1)-connected. If not, then H hasa proper separation Ui, U,] of order at most k; put H[Ul =: H,Hi,H2Since any vertex e Ui U, has all its d(v) ≥ (H) > neighboursfrom H in Hi, we have [Hi] ≥≥ 2k. Similarly, [H2] ≥ 2k. As by theminimality of H neither Hi nor H2 satisfies (*), we further haveIH:II≤(H/-k)for i =- 1,2. But thenH≤ IHII+[H2I≤((Hi|+[H2] -2k)≤(H}-)(as |HinH2/ ≤ k)口which contradicts (*) for H1.5 Trees and forestsAn acyclic graph, one not containing any cycles, is called a forest. A con.forestnected forest is called a tree. (Thus, a forest is a graph whose componentstreeare trees.) The vertices of degree 1 in a tree are its leaves.5 Every non-leaftrivial tree has a leaf-consider, for example, the ends of a longest path.This little fact often comes in handy, especially in induction proofs abouttrees: if we remove a leaf from a tree, what remains is still a tree.except that the root ofa tree (see below) is never called a leaf, even if it hasdegree 1.1.4 Connectivity 13 Proof . Put γ := ε(G) ( 2k), and consider the subgraphs G ⊆ G such (1.2.2) (1.3.1) γ that |G | 2k and G > γ  |G | − k  . (∗) Such graphs G exist since G is one; let H be one of smallest order. H No graph G as in (∗) can have order exactly 2k, since this would imply that G > γk 2k2 > |G | 2  . The minimality of H therefore implies that δ(H) > γ : otherwise we could delete a vertex of degree at most γ and obtain a graph G H still satisfying (∗). In particular, we have |H| γ. Dividing the inequality of H > γ |H| − γk from (∗) by |H| therefore yields ε(H) > γ − k, as desired. It remains to show that H is (k + 1)-connected. If not, then H has a proper separation {U1, U2 } of order at most k; put H [Ui ] =: Hi. H1, H2 Since any vertex v ∈ U1
U2 has all its d(v) δ(H) > γ neighbours from H in H1, we have |H1| γ 2k. Similarly, |H2| 2k. As by the minimality of H neither H1 nor H2 satisfies (∗), we further have Hi γ  |Hi| − k  for i = 1, 2. But then H H1 + H2 γ  |H1| + |H2| − 2k  γ  |H| − k  (as |H1 ∩ H2| k), which contradicts (∗) for H.
1.5 Trees and forests An acyclic graph, one not containing any cycles, is called a forest. A con- forest nected forest is called a tree. (Thus, a forest is a graph whose components tree are trees.) The vertices of degree 1 in a tree are its leaves. 5 Every non- leaf trivial tree has a leaf—consider, for example, the ends of a longest path. This little fact often comes in handy, especially in induction proofs about trees: if we remove a leaf from a tree, what remains is still a tree. 5 ... except that the root of a tree (see below) is never called a leaf, even if it has degree 1.