Colorful Mathematics: Part III
4. Breaking the rules
Every maximal planar graph has a combinatorially isosceles coloring.
The key to proving this result is a theorem of Julius Petersen that any 3-valent graph that has no bridge has a disjoint collection of edges that include all the vertices (i.e. a perfect matching). The figure below shows a plane graph all of whose faces are triangles. Below it is a way of coloring the edges of that graph with two colors so that each triangle gets one blue edge and two red edges.
In the diagram above one can interpret the two colors as being edges of different lengths when one attempts to make a convex 3-dimensional polyhedron all of whose faces are congruent isosceles triangles. However, not surprisingly, there are combinatorial types of plane triangulations T for which there is no geometric realization of any combinatorially isosceles coloring of T by a convex 3-dimensional polyhedron where all the triangles are congruent isosceles triangles. Remember that for a given triangulation T there may be many congruent isosceles triangle colorings for T, some of which may be realizable by a polyhedron and some of which may not. An interesting open question growing out of this investigation is the following:
We can describe each A.C. using a triple of numbers, the first being the cost, the second the monthly cost, and the third the weight. Air conditioner A would be described by (275, 47, 43) while B would be described by (380, 44, 40). We will use x R y to mean that A.C. Brand x is clearly superior to Brand y, where x = (x1, x2, x3) and y = (y1, y2, y3). For relationship x R y to hold we need to have that x1 < y1, x2 < y2, and x3 < y3. In the example above, B R C but we can reach no conclusion with regard to either A and B, or A and C with respect to relation R.
The graph H on the left has five vertices labeled v, w, x, y, and z and five edges labeled e, f, g, h, and i. The incidence order P(H) associated with H is shown on the right, with the vertices at the bottom and the edges at the top. A vertex is joined to those edges for which the vertex is an endpoint of that edge. Notice that the valences of the vertices of the original graph are reflected in the valences of the vertices in the bottom row of the graph on the right, while the valence of the vertices in the top row are all two. This reflects the fact that every edge has exactly two endpoints.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance