Uses of the incidence matrix of a graph

Question

The incidence matrix of a graph is a way to represent the graph. Why go through the trouble of creating this representation of a graph? In other words what are the applications of the incidence matrix or some interesting properties it reveals about its graph?

Answer 1

There are many advantages, especially if the total number of edges is $|E| = \Omega(|V|^2)$. First of all, worst-case constant time for adding, deleting edges, also testing if edge exists (adjacency lists/sets might have some additional $\log n$ factors). Second, simplicity: no advanced structures needed, easy to work with, etc. Moreover some algorithms like to store data for each edge (like flows), matrix representation is then very convenient, and sometimes has nice properties like:

• if $A$ contains $1$ for edges and $0$ otherwise, then $A^k$ contains the number of paths of length $k$ between all vertices,
• if $A$ contains weights (with $\infty$ meaning no edge), then $A^k$ using the min-tropical semiring gives you the lightest paths of length $k$ between all the pairs.

Finally, there is spectral graph theory.

I hope this explains something ;-)

Answer 2

Because then one may apply matrix theoretical tools to graph theory problems. One area where it is useful is when you consider flows on a graph, e.g. the flow of current on an electrical circuit and the associated potentials.

Answer 3

Another example is the beautiful Matrix Tree Theorem, which says that the number of spanning trees of a graph is equal to a minor of the Laplacian of the graph, which is a matrix closely related to the incidence matrix.