Four WEIRD Theorems I Learned from Wikipedia

by radimentary

You Won’t Believe How SIMPLE Their Proofs Are!

1. Balinski’s Theorem. If P is a convex d-dimensional polytope, then its skeleton is a d-connected graph. (The skeleton of a polytope is the graph you get from just taking the vertices and edges. A d-connected graph is a graph which is still connected if you delete any d-1 vertices.)

Proof.  Let S be any set of at most d-1 vertices of P, and pick a vertex v \in P outside S. Since S \cup \{v\} contains at most d points, it is contained in a hyperplane H in \mathbb{R}^d, and there is a linear functional f which is zero on H but nonzero outside it. Call a point positive if f 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 f-maximizing vertex v_+, and each move along this path only increases the value of f. Thus v and every positive point is connected to v_+ by a path of only positive points. Similarly, v and every negative point is connected to the f-minimizing vertex v_- by only negative points. Thus every vertex outside S is connected to v.

2. The De Bruijn–Erdős Theorem. If all finite subgraphs of an infinite graph G are k-colorable, then so is G(A graph is k-colorable if it has a proper k-coloring, i.e. an assignment of integers up through k to vertices so that adjacent vertices have different colors.)

Proof. Proper colorings of G=(V,E) are functions V \rightarrow [k], which we can think of as points in X = [k]^V. Under the product topology, X is compact by Tychonoff’s theorem. For any finite subgraph H of G, denote by X_H the (closed) subset of functions in X which properly color H. By the assumption, X_H is nonempty. Furthermore, any finite intersection of X_H‘s is itself and X_H and is nonempty. Thus, by compactness the mutual intersection of all the X_H‘s is nonempty. Any common intersection is a proper coloring of G.

3. Frucht’s Theorem. Every finite group is the automorphism group of a finite simple graph.

Proof. For a finite group G, pick a set of generators S and construct the (directed) Cayley graph H = \Gamma(G, S), the graph whose vertex set is G and edges are drawn between elements differing by an element of S. 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) H are given by multiplication by elements of G, and so Aut(H) = G.

It remains to convert H into an honest uncolored, undirected graph. This can be done by choosing |S| 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 G is equal to the minimum number of vertices, over all orientations of G, in the longest oriented path in G(An orientation of an undirected graph G is a directed graph obtained by giving each edge in G a direction.)

Proof. If G has a proper k-coloring, orient each edge to go from the smaller color to the larger color. Then, every oriented path in this orientation contains at most k vertices.

In the opposite direction, suppose we have an orientation H of G for which every oriented path contains at most k vertices. Pick a maximal acyclic subgraph H_0 \subseteq H, i.e. keep adding edges that don’t form an oriented cycle until you can’t. Color each vertex of G by the length of the longest path of H_0 ending in that vertex. This will be a proper k-coloring of G.