Mac Lane's planarity criterion

In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who published it in 1937. It states that a finite undirected graph is planar if and only if the cycle space of the graph (taken modulo 2) has a cycle basis in which each edge of the graph participates in at most two basis vectors.

For any cycle c in a graph G, one can form an m-dimensional 0-1 vector that has a 1 in the coordinate positions corresponding to edges in c and a 0 in the remaining coordinate positions. The cycle space C(G) of the graph is the vector space formed by all possible linear combinations of vectors formed in this way. In Mac Lane's characterization, C(G) is a vector space over the finite field GF(2) with two elements; that is, in this vector space, vectors are added coordinatewise modulo two. A 2-basis of G is a basis of C(G) with the property that, for each edge e in G, at most two basis vectors have nonzero coordinates in the position corresponding to e. Then, stated more formally, Mac Lane's characterization is that the planar graphs are exactly the graphs that have a 2-basis.

One direction of the characterisation states that every planar graph has a 2-basis. Such a basis may be found as the collection of boundaries of the bounded faces of a planar embedding of the given graph G.

If an edge is a bridge of G, it appears twice on a single face boundary and therefore has a zero coordinate in the corresponding vector. Thus, the only edges that have nonzero coordinates are the ones that separate two different faces; these edges appear either once (if one of the faces is the unbounded one) or twice in the collection of boundaries of bounded faces. It remains to prove that these cycles form a basis. One way to prove this by induction. As a base case, G is a tree, then it has no bounded faces and C(G) is zero-dimensional and has an empty basis. Otherwise, removing an edge from the unbounded face of G reduces both the dimension of the cycle space and the number of bounded faces by one and the induction follows.

...
Wikipedia