3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ There is no $2$-dimensional holes in a $1$-dimensional object. What being non-planar doesn't mean there are $2$-dimensional "holes," it means that there is no embedding onto the plane. There might be an embedding into another space with no holes - indeed, all graphs can be embedded in $3$ dimensions. $\endgroup$ – Thomas Andrews Dec 4 '16 at 15:21
  • $\begingroup$ A two dimensional hole would intuitively have a boundary that looks like a surface. A graph doesn't contain anything that looks like a surface. It is purely $1$-dimensional. $\endgroup$ – Matt Samuel Dec 4 '16 at 15:27
  • $\begingroup$ Nonplanar graphs can have odd Betti numbers as well. Really not being planar has very little to do with homology, though it does imply that there are some cycles. $\endgroup$ – Matt Samuel Dec 4 '16 at 15:29
  • $\begingroup$ @MattSamuel I'm not sure if this clarifies anything, or will just provoke more corrections, but I realize that "two-dimensional hole" doesn't capture well what I am trying to say -- I mean "a cavity analogous to that bounded by the 2-sphere, analyzed by the second homology group, consisting of a three-dimensional set of points" and when I say a non-planar graph has such a hole, the closest to rigorous statement I can think of is that it possesses an "allowable" or "nice" or "intrinsic" extension to a 2-dimensional CW complex which has such a hole. $\endgroup$ – Chill2Macht Dec 4 '16 at 17:00
  • $\begingroup$ @MattSamuel Also you are right (thank you for correcting/teaching me this) about the odd Betti numbers -- I was assuming an additivity property which I don't have any reason to exist (because it doesn't), I think based in part by being mislead by simple examples. I will leave the original false proof up with a note explaining the mistake. $\endgroup$ – Chill2Macht Dec 4 '16 at 17:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think this is the correct approach to the problem. Skimming through the first chapters of Bonnington and Little's Foundations of Topological Graph Theory, it seems like there is a result (Corollary 3.10 on p. 51) showing that a graph is planar if and only if its Euler characteristic is 2, with the "faces" of the graph being defined by taking the extension of the graph to some 2-complex called a "gem" or a "3-graph" (actually I'm not sure what these are from their definitions yet). $\endgroup$ – Chill2Macht Dec 5 '16 at 12:26
  • $\begingroup$ Also relevant (I think): en.m.wikipedia.org/wiki/Rotation_system, and math.stackexchange.com/questions/206414/… and the links within $\endgroup$ – Chill2Macht Dec 5 '16 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.