Chapter numbers refer to the text by Harris, Hirst, Mossinghoff.

1. Graph Basics (Ch 1.1−1.2)
   Let G = (V,E) be a graph with |V| = n vertices and |E| = m edges.
   • Degree formula:   ∑ deg(v) = 2m
   • Trees, complete graph K_n, bipartite graphs (⇔ no odd cycles), complete bipartite graph K_r,s
   • Cayley's Formula:  The number of trees on n labeled vertices is nⁿ⁻²
     Prüfer Correspondence:  Tree T on vertices {1,2,...,n}  ↔  sequence σ = (a₁,...,a_n−2), where 1 ≤ a_i ≤ n

2. Planarity (Ch 1.3)
   Let G be a planar graph with n vertices, m edges, and r regions.
   • Euler's Formula:  If G is a connected planar graph, then n − m + r = 2.
   • Degree inequality:   gr ≤ ∑ deg(R) ≤ 2m , where girth g = shortest length of a cycle of G.
   • Maximal planar graphs:  Every region of G is a triangle. G has:  m = 3n−6,  r = 2n−4,  3r = 2m .
   • Kuratowski's Theorem:  A graph is planar if and only if it contains no edge-subdivision of K_3,3 or K₅ .

3. Graph coloring (Ch 1.4.1−1.4.3)
   
   • Proper coloring:  Adjacent vertices must get different colors.Equivalent to many scheduling and distribution problems.
   • Chromatic number:  χ(G) = smallest number of colors in a proper coloring.
   • 2-Coloring:  χ(G) = 2 if and only if G is bipartite (and has edges)
   • Greedy algorithm:  Color the vertices one by one, always choosing the first color not conflicting with previously colored vertices.In general, this produces a non-minimal proper coloring with at most Δ(G) + 1 colors, where Δ(G) is the largest vertex-degree of G.
   • Lower bounds for χ(G):  If G ⊃ H a subgraph, then χ(G) ≥ χ(H) .  If G ⊃ K_k a complete graph, then χ(G) ≥ k . If ind(G) is the maximal size of an independent set of vertices (no adjacencies), then χ(G) ≥ n / ind(G) .
   • Wheel construction: If we construct G* by connecting one new vertex to all vertices of G, then χ(G*) = χ(G) + 1 .
   • Four Color Theorem:  If G is planar, then χ(G) ≤ 4 . 
   • Chromatic polynomial: p_G(k) = # proper k-colorings of G ≥ 0 .
   • For T a tree, p_T(k) = k(k-1)^n-1. For G = C_n , p_G = (k−1)ⁿ + (−1)ⁿ(k−1).
   • For G = (V,E) and S ⊂ E, consider the subgraph G_S = (V,S). Let comp( ) denote the number of connected components. Then: p_G(k) = ∑_S⊂E (−1)^|S| k^comp(G_S) .

Problems  

1. Explicitly compute the Prufer Correspondence between the 4² = 16 trees on 4 vertices and the 16 sequences σ = (1,1), (1,2), ... , (4,4)
2. Extra Credit: In HHM Fig 1.22 (p 14), they have drawn the isomorphism classes of trees on n vertices for n ≤ 6: that is, the different shapes of trees without labels on the n vertices. (Any of the n^n-2 trees on n labelled vertices is isomorphic to one of the types listed.) Continue this drawing for n = 7,8,... as high as you can. Can you find any kind of pattern in the number of such classes?
3. For each class of graphs G, find the maximum possible number of edges it could have. Explicitly describe a maximal graph.
   1. G is a bipartite graph with n = 10 vertices.  Ans: q = 25.
   2. G is a connected and acyclic with n = 10 vertices.  Ans: q = 9.
   3. G is acyclic and regular with n = 10 vertices.  Ans: q = 5.
   4. G is 5-regular with n = 10 vertices. Ans: q = 25.
   5. G is maximal planar with n = 10 vertices. Ans: q = 24.
   6. G is planar, vertex-regular and region-regular. Ans: q = 30.
4. Let G = K₅ − e be the complete graph with one edge deleted.
   1. Show that this graph is planar using Kuratowski's Theorem.
   2. Show that G is planar by giving a plane drawing without crossing edges.
   3. Give a proper coloring of G with 4 colors (possible by the Four Color Theorem). Draw a map with 5 countries whose dual graph is G.