Graphs: trees, planarity and Ramsey
Tonight's idea
A graph is dots (vertices) joined by lines (edges). The degree of a vertex is the number of edges at it; adding up all the degrees counts every edge twice, so the degrees sum to \(2E\).
Trees. A tree is a connected graph with no cycles. Every tree with \(n\) vertices has exactly \(n - 1\) edges. Induction: one vertex, no edges. A bigger tree has a leaf, a vertex with only one edge (walk without repeating vertices; where you get stuck is a leaf). Remove the leaf and its edge: a tree with \(n - 1\) vertices, which by induction has \(n - 2\) edges. Put the leaf back: \(n - 1\).
Planarity. A graph is planar if it can be drawn with no edges crossing. Euler's formula says a connected planar drawing has \(V - E + F = 2\), where \(F\) counts regions including the outside. With \(V \ge 3\), count (edge, region) pairs: at least 3 per region, at most 2 per edge, so \(3F \le 2E\). Substitute \(F = 2 - V + E\):
\(E \le 3V - 6\) for every planar graph with \(V \ge 3\). With no triangles, regions need 4 edges and \(E \le 2V - 4\).
\(K_5\) (five vertices, all ten pairs joined) has \(10 > 9\): it cannot be drawn flat. The utility graph \(K_{3,3}\) (three houses, three utilities, nine lines) has no triangles and \(9 > 8\): impossible too.
Watch one: \(K_5\) minus an edge
Remove one edge from \(K_5\): \(V = 5\), \(E = 9\), and \(E \le 3V - 6 = 9\) holds. That only says "not ruled out"; to show it is planar you must draw it. Let the missing edge be 45. Draw 1, 2, 3 as a triangle, put 4 inside joined to 1, 2, 3, and 5 outside joined to 1, 2, 3. Nine edges, no crossings.
Check Euler: \(F = 2 - 5 + 9 = 6\). On the drawing: three regions inside, two outside between the spokes, and the unbounded one. Six.
Your turn
- A tree has 12 vertices. How many edges? A connected graph has 12 vertices and 15 edges; how many edges must you delete to leave a tree?
- Check Euler's formula on the cube (8 corners, 12 edges, 6 faces). The dodecahedron has 20 vertices, each of degree 3: find \(E\) from the degrees, then \(F\).
- In a tree every vertex has degree 1 or 3. With \(L\) leaves and \(T\) vertices of degree 3, add up the degrees (the total is \(2E = 2(n-1)\)) to prove \(L = T + 2\). Why can no such tree have 7 vertices?
- Use \(E \le 3V - 6\) to prove every planar graph has a vertex of degree at most 5. (Suppose every degree were \(\ge 6\) and add up the degrees.)
Stretch: the party of six
Prove that among any six people there are three who all know each other or three who are all strangers. Hint: colour the edges of \(K_6\) red (know) or blue (strangers). Pick a person \(A\); of her 5 edges, at least 3 share a colour. Now look at the triangle those three edges point to. Draw five people for whom it fails.
Answers
- 11 edges. Delete \(15 - 11 = 4\) edges, each breaking a cycle without disconnecting the graph; which four matters, the number does not.
- Cube: \(8 - 12 + 6 = 2\). Dodecahedron: degree sum \(60 = 2E\), so \(E = 30\); \(F = 2 - 20 + 30 = 12\), the twelve pentagons.
- \(n = L + T\) and \(L + 3T = 2(n-1) = 2L + 2T - 2\), so \(T = L - 2\). Then \(n = 2T + 2\) is even, so 7 is impossible.
- If every degree were \(\ge 6\), then \(2E \ge 6V\), so \(E \ge 3V\). But \(E \le 3V - 6 \lt 3V\). Contradiction.
Stretch. Say \(A\) has three red edges, to \(B, C, D\). If any of \(BC, CD, BD\) is red, it makes a red triangle with \(A\); if none is, \(BCD\) is a blue triangle. Five people are not enough: colour a pentagon red and its inner pentagram blue; every triangle uses both colours. In Ramsey notation, \(R(3,3) = 6\).