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?

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.

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$)