Uses of the incidence matrix of a graph 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?

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