# Gauss-Bonnet Theorem for Graphs?

One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an n-cycle has χ = 0 and K4 has χ = –2.
Is there an analog for the Gauss-Bonnet theorem for graphs, something akin to:
[total turn angle] + [enclosed curvature] = τ + ω = 2 π χ ?
Certainly if one embeds the graph on a manifold, then an interpretation is possible via Gauss-Bonnet on the manifold. But is there a more purely combinatorial interpretation?

Addendum. (27Nov11). A new paper on this topic just appeared on the arXiv: Oliver Knill (who answered below back in March), "A graph theoretical Gauss-Bonnet-Chern Theorem." arXiv:1111.5395v1. Here is Knill's first figure:

-
When you say "embeds the graph in a manifold", do you mean "embeds the graph in a compact surface so that its complement is a disjoint union of disks"? I am having trouble seeing how this would work in a more general situation. –  S. Carnahan May 28 '10 at 14:49
Yes, that is what I meant, your precision is much preferable to my off-hand way of expressing it. –  Joseph O'Rourke May 28 '10 at 15:09
@Joseph: Are you explicitly interested in general graphs - including trees or the graph shown above - or is it OK to consider specific families of graphs, e.g. polyhedral graphs? (I believe that it is possible to have a purely combinatorial interpretation of Gauss-Bonnet for polyhedral graphs, independent of a specific embedding.) –  Hans Stricker Jan 22 '13 at 15:37

One can do the following : given a graph with $n$ vertices and $m$ edges, define the scalar curvature of a vertex $x$ of valency $v(x)$ by $S(x)=2-v(x)$. Isolated and pendant vertices have positive scalar curvature, $S$ vanishes precisely on degree two vertices (wich are those one want to call flat), and is negative for higher degrees, reminiscent of the trees being $\mathrm{CAT}(-\infty)$.

Now $\sum_x S(x)=2n-\sum_x v(x)=2\chi$ is a Gauss-bonnet formula. It is very simple, but one does not expects much more from such local considerations.

I guess that to get a more subtle formula, one can try to add some geometric structure to the graph (for example, a length on each edge and an angle for each pair of adjacent edges, and maybe a circular ordering of the edges incident to each vertex).

-
Very nice! Thanks! Presumably, then, there is a version for, say, a simple cycle in the graph enclosing a certain amount of "scalar curvature." –  Joseph O'Rourke May 28 '10 at 14:51
I like this answer! Intuitively a negative curvature point is one with 'more space than one might expect around it' and a positive curvature point is one with less. Ties up quite nicely I think... –  Tom Boardman May 28 '10 at 15:55

There is indeed a version of Gauss-Bonnet for graphs $G$ embedded on a 2-manifold. Here, the combinatorial curvature at a vertex $x$ of $G$ is

$1-\frac{deg(x)}{2} + \sum_{f \sim v} \frac{1}{size(f)}$,

where $f \sim v$ means that the face $f$ is incident to the vertex $x$.

This paper by Chen and Chen, then gives a Gauss-Bonnet formula for embedded infinite graphs with a finite number of accumulation points.

-