Figure 1
Symmetry
Prepared by:
Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
What makes an image or piece of art visually interesting? Many people find orderly or symmetrical images appealing.
Intuitively, a symmetry of an object X is a mapping of the object onto itself that preserves some property of X. A symmetry of a graph, which is a combinatorial structure in that the lengths of the edges in a representation or drawing of the graph are usually not taken into account, is known as an automorphism. This is a mapping of the vertex set of the graph onto itself which preserves edges. (An automorphism is an isomorphism of a graph with itself.) When a graph is drawn in the plane, whether or not it has accidental crossing (points where edges meet other than vertices), then the drawing can be viewed metrically. In this case we can consider the mapping of the vertices onto the vertices which not only preserves edges but also the Euclidean lengths of the edges. A distance preserving map of a set X onto itself is called an isometry. The isometries of a tiling of the Euclidean plane or a frieze pattern on a strip can have translations, rotations, reflections, or glide reflections as isometries. However, if the set in the Euclidean plane is bounded (can be enclosed in a large circle), then the isometries are limited to rotations and reflections.
Another aspect of symmetry is for a bounded set to have a center of symmetry. It is important to notice that very "symmetrical" sets may not have a center of symmetry. An equilateral triangle has three mirrors (the altitudes of the triangle, which coincide with the medians and perpendicular bisectors of the sides) which meet at a point called the centroid C of the triangle. However, this point is well known to lie at the 2/3 mark from the vertex to the foot of the median. Thus, C does not bisect the median (altitude) in an equilateral triangle. This is despite the fact that one can reflect the equilateral triangle in three different lines and map it onto itself. A point X is a center of symmetry for the plane bounded set Z if for any line l through X the points P and P* where l meets the boundary of Z have X as the midpoint of the segment PP*.
For example, in the parallelogram Z (ABCD) below, there is no mirror line but the point where the diagonals AC and BD meet is a center of symmetry.
Figure 4 below shows a polyhedron (crystal) in a hidden line representation which is centrally symmetric.
To help further understand the distinctions between the automorphisms of a graph and the isometries of different drawings of isomorphic copies of the graph, consider the two drawings of the graph K4 shown in Figure 5.
While both the drawings are isomorphic copies of K4, the symmetry groups of the two diagrams are not the same. The graph on the left has 6 symmetries while the graph on the right has 8 symmetries. In terms of their groups, the diagram on the left has as its isometry group the dihedral group with 6 elements (which is also isomorphic to the symmetric group on 3 letters), and the drawing on the right's group is the dihedral group with 8 elements. It is also noteworthy that the graph on the left is plane while the graph on the right is not (though it is planar as the graph on the left shows).
Given a graph we can find its automorphism group. However, suppose that someone gives us a group H and asks if there is a graph which has H as its automorphism group. A remarkable theorem of Roberto Frucht says that this is always possible. Furthermore, an extension of Frucht's Theorem says that there is always a 3-valent graph whose automorphism group is H.
Steinitz's Theorem says when a graph G is the vertex-edge graph of some 3-dimensional convex polyhedron. The statement of the theorem is that G is the vertex-edge graph of some 3-dimensional convex polytope if and only if G is planar and 3-connected. What does 3-connected mean for a graph without loops and multiple edges? A connected graph has at least one path from any vertex to any other vertex. A k-connected graph has at least k paths from any vertex to any other vertex where the paths have in common only the start and terminal vertices of the paths. Thus, a 3-connected graph has at least 3 paths between every pair of vertices (that share only the start and end vertices). Note that 3-connected graphs have vertices which are 3-valent or more. Unfortunately, there is no analogue of Frucht's Theorem for planar 3-connected graphs. Laszlo Babai (U. of Chicago) has pointed out that there is no convex 3-dimensional polyhedron whose vertex-edge graph has the 8- element quaterion group as its automorphism group.
Peter Mani showed that if G is a planar 3-connected graph and H is the automorphism group of G, then one can construct a 3-dimensional convex polyhedron P such that the group of isometries of P is isomorphic to H. Thus, the full symmetry (automorphism) group of a graph that gives rise to convex 3-dimensional polyhedra is no larger than the isometry group of some way of constructing a convex polyhedron with this graph in 3-space. However, suppose that H* is a subgroup of H, the full automorphism group of a planar 3-connected graph. There is no guarantee that there is a combinatorially equivalent polyhedron to P, a polyhedron that has H as its group of isometries, which has H* as its isometry group!
To help understand what is going on here it might help to look at two dimensions rather than three dimensions. Suppose one has a convex 4-gon in the plane. What symmetry groups can it have?
The graph of this convex 4-gon is a 4-cycle, so as a graph its automorphism group is the dihedral group which I will denote D(4) which has 8 elements. Now there is a convex 2-dimensional polygon which has this as its group, namely a square. However, the group D(4) has a cyclic subgroup of order 4, yet there is NO convex 4-gon which has the cyclic group of order 4 as its set of isometries. There is a rectangle with unequal sides which has a group of order 4 as its symmetry (isometry) group but this is the Klein group, not the cyclic group, of order 4.
Exercise: For various plane convex 4-gons that you are familiar with (square, rectangle, isosceles trapezoid, kite, etc.) what is the isometry group of such 4-gons? (Remember that the automorphism group of the graph of a 4-cycle has 8 elements.)
Coming back to 3-dimensions and Mani's Theorem, a similar thing can happen. The isometry group of 3-dimensional cube (all edges of the same length and all the faces congruent squares) is a group with 48 elements which is the same as the automorphism group of the graph of the 3-cube. However, there is a subgroup of order 24 of this group with 48 elements which corresponds to all the rotation of the {regular) 3-cube, but there is no 3-dimensional convex polyhedron which is combinatorially a 3-cube which has 24 isometries!
References:
P. Mani, Automorphismen von polyedrischen Graphen, Math. Ann. 192 (1971) 279–303.