Final Exam Review II - Solutions

Final Review Problems II

  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 = (1)(234), ρ2 = (2)(134), etc., which rotate each of the faces by 120°. 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.
      Solution: The 12 elements of G are:
      identity1 = (1)(2)(3)(4)
      120° face 1ρ1 = (1)(234)
      −120° face 1ρ12 = (1)(432)
      120° face 2ρ2 = (2)(134)
      −120° face 2ρ22 = (2)(431)
      120° face 3ρ3 = (3)(124)
      −120° face 3ρ32 = (3)(421)
      120° face 4ρ4 = (4)(123)
      −120° face 4ρ42 = (4)(321)
      180° edges 14 & 23ρ1ρ2 = (14)(23)
      180° edges 12 & 34ρ2ρ3 = (12)(34)
      180° edges 13 & 24ρ4ρ3 = (13)(24)

    2. Use Burnside's Formula to find N(k), the number of symmetry classes of k-colorings of the four faces. 
      Solution: N(k) = 1/|G| ∑π∈G kcyc(π) =  1/12 (k4 + 11 k2) .

  2. The NATO logo is a four-pointed star divided into 8 regions as shown.
    1. Product Principle: k8
    2. Chromatic polynomial of n-cycle G = Cn is cG(k) = (k−1)n + (−1)n(k−1). The NATO logo is equivalent to G = C8. Ans: (k−1)8 + k − 1
    3. The symmetry group of this shape is Γ = D4, the same as the 4 rotations and 4 reflections of a square. How many ways are there to color the 8 regions with k colors, counting symmetric colorings the same?

      Solution: Since there are 8 regions to be colored, we think of Γ ⊂ S8 . The 8 elements of Γ permute the 8 regions as:

      identity1 = (1)(2)(3)(4)(5)(6)(7)(8)
      90°ρ = (1357)(2468)
      180°ρ2 = (15)(26)(37)(48)
      270°ρ3 = (7531)(8642)
      reflectτ1 = (18)(27)(36)(45)
      reflectτ2 = (12)(38)(47)(56)
      reflectτ3 = (14)(23)(58)(67)
      reflectτ4 = (16)(25)(34)(78)

      Thus Burnside gives: N(k) = 1/8 (k8 + 5 k4 + 2 k2).

  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 bipartite. Clearly G should be a complete bipartite graph since we want a maximal number of edges. Now, Kr,s has q = rs edges, and if r + s = 10, this is maximized for r = s = 5. Thus q = 52 = 25.
    2. G is connected and acyclic. Connected and acyclic means G is a tree, with q = n−1 = 9.
    3. G is acyclic and regular. Acyclic means that every connected component of G is a tree T. Unless T is a single point, it must have a leaf, meaning deg(v) = 1. Since T is regular, every vertex must be a leaf, meaning T must be a single edge. We can draw at most q = 5 disconnected edges on 10 vertices.
    4. G is 5-regular. The number of edges of a d-regular graph is: q = ½ ∑ deg(v) = ½dn, so in this case q = ½(5)(10) = 25.
    5. G is maximal planar. Then q = 3n − 6 = 24.
    6. G is non-planar. The complete graph G = K10 is non-planar, since it contains K5, and it has the most edges of any graph (not only non-planar): q = (10 | 2) = 45.
    7. G can have any value of n, and it is planar, vertex-regular, and region-regular. Then G is a Platonic graph. The largest of these is the icosohedron with vertex-degree d = 5 and region-degree g = 3. Drawing the graph using our method (starting with the outside triangle) shows that q = 30.