Final Exam Review II

The best preparation for the exam is to review the Quizzes, HW, and Tests, making sure to understand your mistakes. The material below is to give you extra practice on the most important topics.

• Coloring with symmetry (Ch 2.5.1−2.5.3)
  • An object X with n vertices V, having symmetry group Γ = Sym(X) ⊂ S_n ; where we consider each symmetry as defined by how it permutes the vertices.
  • Multiplication of permutations and symmetries
  • Problem: Color each of the n vertices of X with one of k colors. Find the number of such colorings, counting symmetric colorings as the same: i.e., find N(k) = # symmetry classes of colorings of X.
  • Burnside's Formula:    N(k) = ¹/_|Γ| ∑_π∈Γ |C_π| = ¹/_|Γ| ∑_π∈Γ k^cyc(π) .
    Here C_π = { colorings fixed by the symmetry π } and cyc(π) = # cycles of the symmetry π ∈ S_n .

• Graph Basics (Ch 1.1−1.2)
  • Trees, complete graph K_n , bipartite graphs, complete bipartite graph K_r,s
  • Cayley's Formula:  The number of trees on n labeled vertices is nⁿ⁻²
    Prüfer Correspondence:  Tree T with vertices V = {1,2,...,n}  ↔  sequenceσ = (a₁,...,a_n−2), where a_i ∈ V

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

• 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 .
  • 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 . 

Final Review Problems II   Turn in the marked problem for Extra Credit.

1. The tetrahedron is a pyramid with 3 sides and a bottom, with each face an equilateral triangle. We want to color the faces, counting two colorings the same if one can be rotated to the other. (We do not allow reflections.)
   1. First, determine the group G of all rotations of the tetrahedron. Label the faces 1,2,3,4, and write a symmetry as a permutation of the faces in cycle notation. We have obvious symmetries ρ₁ = (1)(234), ρ₂ = (2)(134), etc., which rotate each of the faces by 120°. Write ρ_i and ρ_i² for i = 1,2,3,4.
      Surprisingly, these (along with the identity) are not all the symmetries in G. Find the other symmetries by multiplying all pairs ρ_iρ_j, expressing the result in cycle notation. The new elements are the 180° rotations around the axes connecting the midpoints of two opposite sides. Write a complete list of elements of G. Hint: There should be 12 of them. For example, ρ₁ρ₂ = (14)(23) .
   2. Use Burnside's Formula to find N(k), the number of symmetry classes of k-colorings of the four faces.  Ans: ¹/₁₂ (k⁴ + 11 k²)

2. The NATO logo is a four-pointed star divided into 8 regions as shown.
   1. How many arbitrary colorings are there of the 8 regions with k colors? (Arbitrary means with no restrictions.) Ans: k⁸ .
   2. How many proper colorings are there, in which adjacent regions must have different colors? Ans: (k-1)⁸ + k - 1 .
   3. The symmetry group of this shape is Γ = D₄, the same as the 4 rotations and 4 reflections of a square. How many arbitrary colorings are there, counting symmetric colorings the same? Ans: ¹/₈ ( k⁸ + 5k⁴ + 2k² ).
   4. Extra Credit: Finally, how many proper colorings are there, counting symmetric colorings the same? Hint: Apply the main Burnside Theorem (not just the corollary) to proper colorings, so that the formula involves the set PC_π, the proper colorings fixed by a symmetry π ∈ Γ . These sets are counted by the chromatic polynomial of an 8-cycle, a 4-cycle, and a single edge K₂ . Ans: ¹/₈ ( k⁸ - 8 k⁷ + 28 k⁶ - 56 k⁵ + 71 k⁴ - 60 k³ + 36 k² - 12 k ) .

3. Let G be a graph with n = 10 vertices, satisfying some extra condition as listed below. For each class of graphs, 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 non-planar with n = 10 vertices. Ans: q = 45.
   7. Now G is planar, vertex-regular and region-regular. Ans: q = 30.