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.7.1−2.7.2)
  • Permutations in two-line and cycle notation.
  • An object X has n special parts V (often vertices), having symmetry group Γ = Sym(X) inside S_n ; where we consider each symmetry as defined by how it permutes the vertices. (Use gamma Γ for a group to distinguish from a graph.)
  • Composition operation (multiplication) on permutations and symmetries
  • Color each of the n vertices of X with one of k colors possibly with some restrictions: C inside {c : V → K}, where K is the set of colors, and we consider a coloring as a function which assigns a color c(i) to each vertex i.
    Problem: Find the number of such colorings, counting symmetric colorings as the same: i.e., find |C| = # symmetry classes of colorings of X.
  • Burnside's Formula:     |C|   =   ¹/_|Γ| ∑_σ∈Γ |C_σ|   =   ¹/_|Γ| ∑_σ∈Γ k^cyc(σ) ,
    where C_σ = { colorings fixed by the symmetry σ }, and cyc(σ) = # cycles of the symmetry σ in S_n

• Graph Basics (Ch 1.1, 1.3)
  • Paths, cycles C_n , connected components of a graph, complete graph K_n
  • Bipartite graphs ⇔ no odd cycles, complete bipartite graph K_r,s
  • Trees: connected acyclic, n vertices & n−1 edges, can be built up one leaf at a time
  • 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

• Planar Graphs (Ch 1.5.1, 1.5.2, 1.5.4)
  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,
  • Kuratowski's Theorem:  G is non-planar ⇔ G contains an edge-subdivision of K_3,3 or K₅ .
  • Platonic Graphs: (d,g) = (3,3) tetrahedron, (3,4) cube, (3,5) dodecahedron, (4,3) octahedron, (5,3) icosahedron

• Graph coloring (Ch 1.6.1−1.6.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 some edges). Thus χ(C_n) = 2 if n even, = 3 if n odd.
  • Greedy algorithm:  Color the vertices v₁,...,v_n one by one, always choosing the first color not conflicting with previously colored vertices. At the i^th step, if vertex v_i has d neighbors already colored, we need at most a (d+1)^th extra color for c(v_i) . In general, this produces a non-minimal proper coloring, but it can be optimized by removing vertices of small degree.
  • Lower bounds for χ(G):  If G contains a subgraph H, then χ(G) ≥ χ(H) .  If G contains a complete graph K_k, 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 . 

  See Graph Notes.

  ---

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

  1. Consider a tree T with vertices V = {1,...,6} and edges E = {13, 23, 34, 45, 46}. A graph symmetry is a permutation of the vertices σ : V → V which sends each edge e = ij in E to an edge e' = σ(i)σ(j) in E. For example, the symmetry α = (12)(3)(4)(5)(6) switches the edges 13 and 23, and takes every other edge to itself, so α is a graph symmetry. However, φ = (13)(2)(4)(5)(6) takes the edge e = 23 to φ(2)φ(3) = 21, which is not an edge of T, so φ is not a graph symmetry. Imagine the graph as made of wire which can be moved or twisted by graph symmetries. Let Γ = Sym(T) denote the group of all graph symmetries.
     1. Show that |Γ| ≤ 8. Hint: σ(i) must have the same degree as i. Thus σ(3) must be 3 or 4, and σ(1) must be one of the leaves attached to σ(3), etc.
     2. Starting with the two obvious symmetries α = (12)(3)(4)(5)(6) and τ = (15)(26)(34), list all 8 symmetries in Γ.
     3. How many colorings C = {c : V → K} , where K is a set of k colors, and we put no restriction on c?
     4. How many symmetry classes of all colorings?
     5. How many proper colorings PC? Hint: use the Product Principle.
     6. Extra Credit: How many symmetry classes of proper colorings?
        Hint: In Burnside's Formula, instead of |C_σ| use |PC_σ| , the number of proper colorings fixed by each permutation σ ∈ Γ.

  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.)
     2. 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?
     3. How many proper colorings are there, in which adjacent regions must have different colors? (Adjacent means sharing a border, not just a corner.) Hint: Use PIE with A = {all colorings}
     4. Extra Credit: Finally, how many proper colorings are there, counting symmetric colorings the same? Hint: Apply the main Burnside Theorem to proper colorings . As in 1(f), use PIE to count the σ-fixed proper colorings, which are all proper colorings of an 8-cycle, a 4-cycle, or 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 q it could have. That means: (i) prove there could not be any such graph with more than q edges; and (ii) explicitly describe such a graph to show that the maximum is achieved.
     1. G is non-planar.
     2. G is a bipartite graph.
     3. G is acyclic.
     4. G is acyclic and regular.
     5. G is 5-regular.
     6. G is maximal planar.
     7. G is bipartite and planar. Hint: Use the Region-Edge Inequality.

  ---

  Answers

  1. Tree symmetries
     1. Since 1,2,4 are the only neighbors of 3, we must have σ(1), σ(2), σ(4) the only neighbors of σ(3). Thus σ(3) must be a vertex of degree 3, namely σ(3) = 3 or 4 (two choices). Similarly σ(1) is a degree-one neighbor of σ(3), so it has two choices, and σ(5) also has two choices. This makes 2 × 2 × 2 = 8 choices for σ(3), σ(1), σ(5), which determine every other σ(i).
     2. The four symmetries coming from moving the graph rigidly are the same as those of a rectangle: ε = (1)(2)(3)(4)(5)(6), τ = (15)(26)(34), σ = (12)(3)(4)(56), ρ = (16)(25)(34). We can get the other four by multiplying by α: α = (12)(3)(4)(5)(6) , ατ = (1526)(34) , ασ = (1)(2)(3)(4)(56) , αρ = (1625)(34).
     3. Colorings: kⁿ = k⁶
     4. Symmetry classes of colorings: |C| = ¹/_|Γ| ∑_σ∈Γ k^cyc(σ) = ¹/₈(k⁶ + 2k⁵ + k⁴ + 2k³ + 2k²), where cyc(σ) is the number of cycles in σ acting on V = {1,...,6}, including cycles of length one (fixed points).
     5. Proper colorings: product principle for successively choosing c(1), c(2),... gives: k(k−1)...(k−1) = k(k−1)⁵.
     6. |PC_ε| = k(k−1)⁵ , since every proper coloring is fixed by the identity. |PC_τ| = 0 , since if c is a proper coloring, then c(3) ≠ c(4), but if c is fixed by τ, then c(3) = c(4). |PC_σ| = k(k−1)³ , since the independent choices are c(1) = c(2), c(3), c(4), c(5) = c(6). Similarly, |PC_ρ| = 0 , |PC_α| = k(k−1)⁴ , |PC_ατ| = 0 , |PC_ασ| = k(k−1)⁴ , |PC_αρ| = 0 .
        Final answer: |PC| = ¹/₈ (k(k−1)⁵ + 2k(k−1)⁴ + k(k−1)³).
  2. Coloring the star.
     1. Colorings: k⁸.
     2. The group contains the identity, three rotations, four reflections. Numbering the regions 1,...,8 clockwise from top left, the symmetries are: Γ = { ε , (1357)(2468), (15)(26)(37)(48), (7531)(8642),                                                    
        (12)(38)(47)(56), (14)(23)(58)(67), (16)(25)(34)(78), (18)(27)(36)(45) } Coloring classes: |C| = ¹/₈(k⁸ + 5k⁴ + 2k²) .
     3. Proper colorings: PIE with A = all colorings, A_i = colorings with region i having the same color as region i+1. Then |A₁| = k⁷, since the idependent choices are c(1) = c(2), c(3),..., c(8). Similarly, |A₁∩...∩A_j| = k^8-j, but |A₁∩...∩A₈| = k. Thus, PIE gives: k⁸ − (8|1) k⁷ + (8|2) k⁶ − … − (8|7) k + k = (k−1)⁸ + k − 1.
  3. Maximal graphs
     1. The maximum possible number of edges in any graph is (n | 2) = (10 | 2), and this is achieved by the complete graph K₁₀, which is non-planar by Kuratowski's Theorem (K₁₀ contains K₅ as a subgraph). Ans: q = 45.
     2. Clearly G must be a complete bipartite graph K_r,10−r, having q = r(10−r) = 10r − r². This is maximal at r = 5, giving q = 25, which is achieved by K_5,5. Ans: q = 25.
     3. An acyclic graph is a forest (with components which are trees), and it has q = n−k, where k is the number of components. This is maximal when k = 1 and G is a tree, and has q = n−1. Ans: q = 9.
     4. If G is acyclic, it is a forest, whose components are trees. Any tree (except a single vertex) has leaves of degree 1. If G is regular, all vertices must have the same degree, which must be d = 1. A 1-regular graph is a union of disconnected edges. Matching pairs of vertices into edges gives q = 10/2 = 5. Ans: q = 5.
     5. If G is regular of degree d = 5, then the Vertex-Edge Formula gives q = ½nd = 25. This is achieved by the graph with vertices V = {v₀, v₁,...,v₉} and edges e = v_iv_j with j = i−2, i−1, i+1, i+2, or i+5 (all modulo 10). Ans: q = 25.
     6. Maximal plannar graphs always have q = 3n−6 = 3(10)−6 = 24. This is not difficult to realize with a plane drawing.
     7. Since G is bipartite, it has no 3-cycles, and girth(G) = g ≥ 4. Thus by the Region-Edge Inequality, 4r ≤ gr ≤ 2q. Furthermore, G is clearly connected (or we could add more edges), so r = 2−n+q, so that 4(2−n+q) ≤ 2q. Solving this, we get q ≤ 2n−4 = 16. This is realized by K_2,8, which is planar since it is easily drawn without edge-crossings (draw the two + vertices to the left and right of a column of eight − vertices). Ans: q = 16.