a partial order (the maximum number of elements in a set of mutually incomparable elements) equals the minimum number of chains (totally ordered subsets) into which the partial order may be partitioned. A partition into chains may be interpreted as a coloring of the incomparability graph of the partial order. This is a graph with a vertex for each element of the order and an edge for each pair of incomparable elements. Using this coloring interpretation, together with a separate proof of Dilworth's theorem for finite partially ordered sets, it is possible to prove that an infinite partially ordered set has finite width if and only if it has a partition into chains. In the same way, the De Bruijn–Erdős theorem extends the four-color theorem from finite planar graphs to infinite planar graphs. Every finite planar graph can be colored with four colors, by the four-color theorem. The De Bruijn–Erdős theorem then shows that every graph that can be drawn without crossings in the plane, finite or infinite, can be colored with four colors. More generally, every infinite graph for which all finite subgraphs are planar can again be four-colored. Proofs The original proof of the De Bruijn–Erdős theorem, by De Bruijn, used transfinite induction. provided the following very short proof, based on Tychonoff's compactness theorem in topology. Suppose that, for the given infinite graph , every finite subgraph is -colorable, and let be the space of all assignments of the colors to the vertices of (regardless of whether they form a valid coloring). Then may be given a topology as a product space , where denotes the set of vertices of the graph. By Tychonoff's theorem this topological space is compact. For each finite subgraph of , let be the subset of consisting of assignments of colors that validly color . Then the system of sets is a family of closed sets with the finite intersection property, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of . A different proof using Zorn's lemma was given by Lajos Pósa, and also in the 1951 Ph.D. thesis of Gabriel Andrew Dirac. If is an infinite graph in which every finite subgraph is -colorable, then by Zorn's lemma it is a subgraph of a maximal graph with the same property (one to which no more edges may be added without causing some finite