|
Introduction. The purpose of this page is to demonstrate a natural way to draw a Tait-colored graph in the real projective plane. For the purpose here, a "Tait-colored graph" is a cubic graph equipped with three mutually-disoint perfect matchings. Thus, if the colors are blue, green, and red, then there is precisely one blue edge, one green edge, and one red edge meeting at every vertex. Given a Tait-colored graph G, define a "projective drawing" of G as a drawing in the real projective plane such that (a) every edge is represented by a line segment and (b) all the lines supporting edges sharing a common color are concurrent. Call a projective drawing "faithful" if all of the supporting lines are distinct. Theorem. A connected bipartite Tait-colored graph with more than 2 vertices has a faithful projective drawing if and only if does not have a 2-edge cut set. The proof of this theorem relies on being able to perturb a projective drawing in an interesting way along cycles in the graph. For example, consider the Cinderella applet: |
|
This represents a projective drawing of the complete bipartite graph K3,3 equipped with a Tait-coloring. (In fact, this is the Pappus configuration.) The three points marked B, G, and R and the 4 black lines are all movable. By moving one of the black lines, one perturbs the drawing along a certain cycle. For example, if one moves the black line containing the edge (2,5), then every point along the cycle (2,5,4,3) is perturbed. This observation lies at the heart of the proof of the theorem above. Given a Tait-colored graph G, define a "forced pair" as a pair π of edges of G such that the vertices of π are collinear in every projective drawing of G. One may show that every 2-edge cut set in a bipartite graph is forced. However, if a bipartite graph has no 2-edge cut set, then there is always a abundance of cycles sufficient enough to allow a sequence of perturbations yielding a faithful drawing. In other words, a 3-connected Tait-colored graph has no forced pairs. Here is another example of a Tait-colored graph with a faithful projective drawing. The Heawood graph also satisfies the hypotheses of the theorem above. Non-Bipartite Graphs. There is a similar characterization for non-bipartite graphs: Theorem. Suppose G is a connected non-bipartite Tait-colored graph. Then a pair π of edges of G is forced if and only if the deleted graph G\&pi has a bipartite component. This case is a little more cumbersome because there are two distinct ways in which a pair π may be forced: Either G\π is connected and bipartite or π is a cut set and exactly one component of G\π is bipartite. Here is an illustration of a forced pair which is not a cut set. Here is an example of a non-bipartite graph with no forced pairs. Higher Degree. Very little is known about what happens when one attempts to draw d-edge-colored d-regular graphs in this manner when d>3. Here is one interesting example. Ghost Symmetry. The characterizations theorems given above were found by considering ghost symmetries. Roughly speaking, one says that an object in a Euclidean space has a "ghost symmetry" if some shadow projection of that object has an unexpected symmetry group. The characterizations above are closely related to another theorem concerning ghost symmetry in the plane.
References. |