Four WEIRD Theorems I Learned from Wikipedia
You Won’t Believe How SIMPLE Their Proofs Are!
1. Balinski’s Theorem. If is a convex -dimensional polytope, then its skeleton is a -connected graph. (The skeleton of a polytope is the graph you get from just taking the vertices and edges. A -connected graph is a graph which is still connected if you delete any vertices.)
Proof. Let be any set of at most vertices of , and pick a vertex outside . Since contains at most points, it is contained in a hyperplane in , and there is a linear functional which is zero on but nonzero outside it. Call a point positive if takes a positive value on it, and negative otherwise.
Now, apply the simplex method from linear programming; it tells us that there is a path from every vertex to the -maximizing vertex , and each move along this path only increases the value of . Thus and every positive point is connected to by a path of only positive points. Similarly, and every negative point is connected to the -minimizing vertex by only negative points. Thus every vertex outside is connected to .
2. The De Bruijn–Erdős Theorem. If all finite subgraphs of an infinite graph are -colorable, then so is . (A graph is -colorable if it has a proper -coloring, i.e. an assignment of integers up through to vertices so that adjacent vertices have different colors.)
Proof. Proper colorings of are functions , which we can think of as points in . Under the product topology, is compact by Tychonoff’s theorem. For any finite subgraph of , denote by the (closed) subset of functions in which properly color . By the assumption, is nonempty. Furthermore, any finite intersection of ‘s is itself and and is nonempty. Thus, by compactness the mutual intersection of all the ‘s is nonempty. Any common intersection is a proper coloring of .
3. Frucht’s Theorem. Every finite group is the automorphism group of a finite simple graph.
Proof. For a finite group , pick a set of generators and construct the (directed) Cayley graph , the graph whose vertex set is and edges are drawn between elements differing by an element of . Color each edge according to which generator it represents multiplication by. Then, it is easy to check that the only automorphisms of the (colored, directed) are given by multiplication by elements of , and so .
It remains to convert into an honest uncolored, undirected graph. This can be done by choosing different “weird gadget” graphs to replace the edges in each color class with. For example, I might replace the edges of the first color with paths of length seventeen with a Petersen graph attached to the fourth internal vertex. As long as these gadgets are weird enough, no additional automorphisms are introduced.
4. The Gallai–Hasse–Roy–Vitaver Theorem. The chromatic number of an undirected graph is equal to the minimum number of vertices, over all orientations of , in the longest oriented path in . (An orientation of an undirected graph is a directed graph obtained by giving each edge in a direction.)
Proof. If has a proper -coloring, orient each edge to go from the smaller color to the larger color. Then, every oriented path in this orientation contains at most vertices.
In the opposite direction, suppose we have an orientation of for which every oriented path contains at most vertices. Pick a maximal acyclic subgraph , i.e. keep adding edges that don’t form an oriented cycle until you can’t. Color each vertex of by the length of the longest path of ending in that vertex. This will be a proper -coloring of .