A brief note on Graph Theory . Read it before a test. Try each question at the end before you open its answer.
Degrees Handshake lemma: ∑ deg v = 2 E \displaystyle\sum \deg v = 2E ∑ deg v = 2 E ; the number of odd vertices is even. Complete graph: K n K_n K n has ( n 2 ) \dbinom{n}{2} ( 2 n ) edges. Two equal degrees in every simple graph with at least two vertices. Connected for sure: more than ( n − 1 2 ) \dbinom{n - 1}{2} ( 2 n − 1 ) edges. Havel–Hakimi: remove the largest degree d d d and subtract 1 1 1 from the next d d d . Trees, bipartite graphs, Euler Tree: connected, no cycle, n − 1 n - 1 n − 1 edges, at least two leaves; forest with c c c trees: n − c n - c n − c edges. Cayley: n n − 2 n^{n-2} n n − 2 labelled trees. Bipartite: no odd cycle. K m , n K_{m,n} K m , n has m n mn mn edges. Mantel: no triangle, at most n 2 4 \dfrac{n^2}{4} 4 n 2 edges. Euler circuit: connected, all degrees even. Euler trail: exactly two odd vertices. Planar graphs, colouring, Ramsey Euler's formula: V − E + F = 2 V - E + F = 2 V − E + F = 2 . Edge bounds: E ≤ 3 V − 6 E \le 3V - 6 E ≤ 3 V − 6 ; no triangle: E ≤ 2 V − 4 E \le 2V - 4 E ≤ 2 V − 4 . K 5 K_5 K 5 and K 3 , 3 K_{3,3} K 3 , 3 are not planar. Colouring: χ ( K n ) = n \chi(K_n) = n χ ( K n ) = n ; bipartite means χ ≤ 2 \chi \le 2 χ ≤ 2 ; odd cycle needs 3 3 3 ; χ ≤ Δ + 1 \chi \le \Delta + 1 χ ≤ Δ + 1 ; planar graphs need at most 4 4 4 . Ramsey: R ( 3 , 3 ) = 6 R(3, 3) = 6 R ( 3 , 3 ) = 6 , R ( 3 , 3 , 3 ) = 17 R(3, 3, 3) = 17 R ( 3 , 3 , 3 ) = 17 . A worked example A connected planar graph has 9 9 9 vertices and 15 15 15 edges. How many faces?
Formula. V − E + F = 2 V - E + F = 2 V − E + F = 2 . Substitute. 9 − 15 + F = 2 9 - 15 + F = 2 9 − 15 + F = 2 . Answer. F = 8 F = 8 F = 8 . Practice with new numbers
A program to try The program checks three facts by trying every case.
Read it first. Then run it. Does the count of trees agree with Cayley's formula?
1. Change the first part to trees on 4 4 4 vertices. Predict the count with n n − 2 n^{n-2} n n − 2 first.
Mistakes to avoid Halving forgotten in the handshake lemma. The outside face left out of F F F . Euler and Hamilton mixed up. A forest treated as a tree. An even degree sum taken as proof that a graph exists. Check yourself How many edges does K 7 K_7 K 7 have? Stuck? Show a hint Show the answerCan a graph have degrees 3 , 3 , 3 , 2 , 2 3, 3, 3, 2, 2 3 , 3 , 3 , 2 , 2 ? Stuck? Show a hint Show the answerA tree has 9 9 9 edges. How many vertices? Stuck? Show a hint Show the answerDoes K 2 , 4 K_{2,4} K 2 , 4 have an Euler circuit? Stuck? Show a hint Show the answerWhat is χ \chi χ of a cycle with 8 8 8 vertices? Stuck? Show a hint Show the answerSources D. B. West, Introduction to Graph Theory , Chapters 1, 2, 5 and 6. R. J. Wilson, Introduction to Graph Theory .