This is a follow-up to [a previous question](https://mathoverflow.net/questions/4912/ "Graphs with incidence matrices whose pseudoinverses are proportional to their transposes"). What graphs have incidence matrices of full rank?


Obvious members of the class: complete graphs.


Obvious counterexamples: Graph with more than two vertices but only one edge.


I'm tempted to guess that the answer is graphs that contain spanning trees as subgraphs. However, I haven't put much thought into this.



Which graphs have incidence matrices of full rank?
The first answer identifies "incidence matrix" with "adjacency matrix". The latter is the
vertices-by-vertices matrix that Sciriha writes about. But the original question
appears to concern the incidence matrix, which is vertices-by-edges. The precise
answer is as follows.


Theorem: The rows of the incidence matrix of a graph are linearly independent over the reals if and only if no connected component is bipartite.


Proof. Some steps are left for the reader :-) 


Note first that the sum of rows indexed by the vertices
in one color class of a bipartite component is equal to the sum of the rows indexed by
the other color class. Hence if some component is bipartite, the rows of the incidence matrix are linearly dependent.


For the converse, we have to show that the incidence matrix of a connected non-bipartite
graph has full rank. Select a spanning tree $T$ of our graph $G$. Since $G$ is not bipartite, there is an edge $e$ of $G$ such that the subgraph $H$ formed by $T$ and $e$ is not bipartite. 


The trick is to show that the columns of the incidence matrix indexed by the edges of H
form an invertible matrix. We see that $H$ is built by "planting trees on an odd cycle".
We complete the proof by induction on the number of edges not in the cycle.


The base case is when $H$ is an odd cycle. It is easy to show that its incidence matrix is invertible. Otherwise there is a vertex of valency one, $x$ say, such that $H \setminus x$ is connected and not bipartite. Then the incidence matrix of $H \setminus x$ is invertible and again it is easy to see this implies that the incidence matrix of $H$ is invertible.


Remark: I do not know who first wrote this result down. It is old, and is rediscovered
at regular intervals.


