Why is homology unable to distinguish between planar and non-planar graphs?

867 Views Asked by At

Intuitively, one can think of non-planar graphs as having a "two-dimensional hole" (Edit: this is both unclear and not entirely, if at all, correct, see comments below question), thus necessitating that they be embedded in space to be represented without self-intersections.

Homology theory is often described intuitively as characterizing the holes of a space. However (see below) one can show rigorously that it is only possible to formulate necessary conditions for non-planarity in terms of the homology groups of a graph, but not sufficient conditions.

Intuitively this might be understood as reflecting the fact that non-planar graphs are characterized by "two-dimensional holes", while the homology groups of any one-dimensional CW complex are trivial (hence provide no information) except for the $0$th and first homology groups.

Question: Is it possible to construe the combinatorial conditions for non-planarity given by Kuratowski's theorem into topological ones which can be verified using homology, say by attaching $2$-cells/simplices to the graph in a standard way? Why or why not?

(For example by forming the independence complex or clique complex, i.e. some way of attaching $2$-cells which is not arbitrary, hence does not provide extraneous information about the graph. This MO question might be relevant.)

Background: Without loss of generality, consider only connected graphs. Then the homology of a (finite) graph is completely determined by its first Betti number (the number of cycles in the graph), which is the rank of the first homology group. The rank of the zeroth homology group is one, and all other homology groups are trivial. (This is implicitly considering graphs as one-dimensional CW complexes, thus by homology I mean any theory satisfying the Eilenberg-Steenrod axioms.)

By Kuratowski's theorem, a graph is non-planar if and only if it contains subgraphs homeomorphic to either $K_5$, the complete graph on five vertices, or $K_{3,3}$, the complete bipartite graph on six vertices.

$K_5$ has $ \frac{5(4)}{2}=10 $ edges, any maximal spanning tree has $4$ edges, thus it must have a Betti number of $10-4=6$. Likewise, $K_{3,3}$ has $3(3)=9$ edges, and any maximal spanning tree must have $5$ edges, so it must have a Betti number of $9-5=4$.

Edit: everything beyond here is wrong -- I was assuming a non-existent additivity property for cycles of a graph based on number of cycles of subgraphs. I.e. over-simplifying reality.

Therefore, any non-planar graph must have: $$4m + 6n = \min\{4,6\} + \gcd\{4,6\}p = 2 + 2r, \, \max\{m,n\}\ge 1, \min\{m,n\} \ge 0, p \ge 0, r \ge 1,$$ for its Betti number, i.e. number of cycles.

On the other hand, we can clearly construct a planar graph with any arbitrary (non-negative integral) number of cycles. Thus we can conclude that non-planar graphs are not uniquely characterized by their homology groups, although we can state as a necessary condition that any non-planar graph must have an even number greater than two as its first Betti number.

1

There are 1 best solutions below

2
On BEST ANSWER

This is an interesting question to me. @ThomasAndrews's comment makes a good point, but there's still something to consider:

When a (connected) graph is embedded in the plane (or, to make things simpler by removing a special case, the sphere), its complement in the plane consists of a bunch of cells (regions homeomorphic to a disk) -- the "regions" bounded by edges. These, together with the graph itself, can be made into a cell complex whose first homology is trivial, and whose second homology is that of a sphere (namely $\Bbb Z$).

What about a (connected) non-planar graph? If you COULD adjoin cells in such a way that the homology "looked right" (i.e., $(\Bbb Z, 0, \Bbb Z)$ in dimensions 0, 1, 2) and so that each edge was joined to exactly two 2-cells (to make it manifold-like), then the resulting manifold would necessarily be a sphere (by the classification theorem for 2-manifolds), and hence the graph would be embeddable, a contradiction.

So the thing you can say is that for a nonplanar connected graph $G$, all possible manifold-like 2-cell complexes whose 1-skeleton is $G$ have homology groups that are not those of the 2-sphere.

Now that's not a very useful statement for the most part, but it does show that homology captures something useful here.