Homology and Graph Theory

What is the relationship between homology and graph theory? Can we form simplicial complexes from a graph $G$ and compute their homology groups? Are there any practical results in looking at the homology of simplicial complexes formed from a graph?

-
The discretized configuration space of a graph is a very interesting cell complex associated to a graph, and the homotopy-theory of it is quite rich. Similarly you can make "graph colouring complexes" associated to graphs and I believe them to be interesting but I don't know if people study this latter topic. For the former topic, look up the work of Rob Ghrist and Aaron Abrams. – Ryan Budney Mar 22 '11 at 15:58

There are a lot of interesting simplicial complexes one can create from a graph. Jakob Jonsson wrote a book called "Simplicial complexes of graphs," which defined a plethora of them. One of my favorite such complexes is the independence complex. The vertex set is the same as that of the graph, and there is a simplex $[v_0,\ldots,v_n]$ whenever no pair of the vertices $v_0,\ldots,v_n$ lie on an edge. It is a fascinating problem to compute the homology even for simple graphs. For example, I would love to know the homology of the independence complex for the 1-skeleton of the n-dimensional cube, but this appears to be a hard problem. Related to the independence complex is the so-called Theta complex which is "Alexander dual" to it in the combinatorial topology sense. See my paper with Oliver Thistlethwaite, where we get our feet wet analyzing the homology of the theta complex of k-skeleta of cubes.

While I'm plugging my own work, there is another notion, called graph homology, in which one constructs an algebraic chain complex whose generators are equivalence classes of decorated graphs. The boundary operator is usually defined by contracting edges of a graph one at a time. As far as I know, this was first considered by Kontsevich. Karen Vogtmann and I give a detailed exposition of various kinds of graph homology here.

-
In the four years since your post, has the (co)homology of the independence complex of the $1$-skeleton of $n$-cube been computed? If yes, what is the formula? – Leon Dec 25 '15 at 14:46
@Leon: I'm unaware of any progress on this question. – Grumpy Parsnip Dec 25 '15 at 21:15

See if you can find a copy of Massey - "A Basic Course in Algebraic Topology". Section VIII.3 is "Homology of Finite Graphs"

Also Hatcher has some stuff - he states that a graph is a 1-dimensional CW complex, and it is indeed possible to take the homology groups.

Here is a nice looking result from Massey (quoted verbatim)

Let $(X,X_0)$ be a finite, regular graph. Then $H_q(X)=0$ for $q>1,H_1(x)$ is a free abelian group and $\mathrm{Rank}(H_0(x))-\mathrm{Rank}(H_1(x)) = \mathrm{Euler \ Characteristic}$ (where here the Euler Characteristic is $V-E$)

-
Also note, that you will have $H_0(X) = \text{free abelian group generated by pathcomponents}$ and $H_1(X) = \text{free abelian group generated by cycles}$ – Alexander Thumm Mar 22 '11 at 6:47

In addition to Qwirk's answer: the result is actually pretty easy to prove.

Let $G$ be a connected graph (otherwise consider its connected components). Consider a spanning tree $T$ of $G$ and let $n$ be the number of edges not in $T$. It's an easy application of the Van Kampen theorem to show that $\pi_1(G,x_0) \cong F_n$ is the free group of rank $n$. Therefore is $H_1(G; \mathbb Z) \cong \mathbb Z^n$ ($H_1$ is the abelianization of $\pi_1$).

Now, since $T$ is a tree we must have $$E - n = V - 1 \implies E - V = n - 1 = \mbox{rk}(H_1(G)) - \mbox{rk}(H_0(G))$$ where $H_0(G) \cong \mathbb Z$ because the graph is connected.

Since $G$ is a one-dimensional CW-complexes the higher homology groups are trivial.

-
Is it possible to prove it using simplicial homology? – Haikal Yeo Apr 30 '13 at 12:37