# Examples of theorems in graph theory

I'm looking for examples of uses of the incidence matrix in graphs for my class (apart from proving that for a graph $G=(V,E)$ we have $2|E|=\underset{v\in V}{\sum}d(v)$). Can you think of anything interesting?
Thanks in advance for any help.

-
Maybe you should mention the background which the students have. Also I have flagged this to make community wiki. – Aryabhata May 3 '11 at 15:30
Is this the incidence matrix or the adjacency matrix you're talking about? – Mitch May 3 '11 at 15:40
What Linear Algebra background do they have? (and possibly other topics). Maybe you should mention something like a US undegraduate: sophomore or something like that too... – Aryabhata May 3 '11 at 15:41
It's the incidence matrix. The linear algebra background is from systems of linear equations up to linear operators, diadonalization , PDT and operators in inner-product spaces. They are first-year undergrads. – Dennis Gulko May 3 '11 at 15:45
@Dennis: the matrix whose powers describe the number of paths of a given length is the adjacency matrix, not the incidence matrix. Which matrix are you talking about? – Qiaochu Yuan May 3 '11 at 16:45

Let $R$ be a commutative ring and $R(V), R(E)$ the free $R$-modules on the vertices and edges, respectively. Pick an orientation of the graph (an arrow attached to each edge pointing from one vertex to the other). The oriented incidence matrix is the matrix of an $R$-module homomorphism

$$\partial : R(E) \to R(V)$$

sending an edge $e$ to $v - w$, where $v, w$ are the vertices in the appropriate orientation. This morphism, and in particular its kernel, is a basic invariant of the graph: when $R = \mathbb{Z}$ or $R = \mathbb{F}_2$ its kernel is the integral (resp. mod $2$) cycle space of the graph, which is a useful tool in answering certain questions in graph theory (the Wikipedia article has references). Abstractly this is a simple example of a simplicial homology group. (Note that you don't have to pick an orientation if $R$ has characteristic $2$. This is familiar behavior from algebraic topology.)

The transpose of the incidence matrix is the matrix of a homomorphism

$$d : R^V \to R^E$$

in the other direction (where $R^S$ is the $R$-module of functions $S \to R$) dual to the above one. It sends a function $f(v)$ on vertices to the function $df(e) = f(v) - f(w)$ on edges and can be thought of as a simple analogue of the derivative. In fact this whole setup is a simple analogue of de Rham cohomology and Hodge theory and one can get the Laplacian naturally this way as well.

The operators above naturally occur if one thinks of graphs as circuits. In fact, Kirchhoff's laws can be naturally stated using them when $R = \mathbb{R}$: an element $I \in \mathbb{R}(E)$ can be interpreted as a list of currents if and only if

$$\partial I = 0$$

and an element $e \in R^E$ can be interpreted as a list of potential differences if and only if there exists $\phi \in R^V$ (the potential) such that

$$d \phi = e.$$

The material about circuits should be in Bollobás' Modern Graph Theory, and for more information Doyle and Snell's Random Walks and Electrical Networks is also worth checking out.

-

A classic example is the Friendship theorem of Erdos and Renyi.

-
I think this one has proofs using both Incidence and Adjacency matrix but I was thinking of the proof using the adjacency matrix when I posted this! – Aryabhata May 3 '11 at 17:02

Eigenvalues of the adjacency matrix provide bounds on the chromatic number $\chi(G)$.

For a graph $G$, let $\mu_\max(G)$ and $\mu_\min(G)$ be the maximum and minimum eigenvalues of the adjacency matrix. Note $\mu_\min(G) < 0 < \mu_\max(G)$ if $G$ is not empty.

All nonempty graphs satisfy $$1 - \frac{\mu_\max(G)}{\mu_\min(G)} \leq \chi(G) \leq \mu_\max(G) + 1.$$

This is proven in Bollobas' Modern Graph Theory.

-
Whoops, you were looking for uses of the incidence matrix, and I provided something regarding the adjacency matrix. I will try to contribute something relevant, too. – Hans Parshall May 3 '11 at 15:53

There is also the classical result that the powers of the adjacency matrix describe the number of paths of a given length between two vertices.

-
Oops, this is about the adjacency matrix, not the incidence matrix. – lhf May 3 '11 at 16:32