Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to know when the row span of $A$ contains the all ones vector in $\mathbb{R}^{|V|}$. I believe this happens if and only if $G$ has a spanning regular subgraph. One direction is of course clear. Does anyone know if this is true/ have a counterexample?



Characterizing graphs whose incidence matrix has the all ones vector in its row span
The rank of the incidence matrix is $|V|$ minus the number of bipartite components. I assume the graph is connected. If it is not bipartite, it follows that the row space is $\mathbb{R}^{V}$ and hence it contains the all-ones vector. If the graph is bipartite, the vector that is 1 on the vertices in the first colour class and $-1$ on the other is orthogonal to each row. So the row space is the orthogonal complement to this vector.


[Edit to deal with Tony's point.] If the colour classes are of equal size, this signed vector is orthogonal to the all-ones vector, and so the all-ones vector is in the row space. Otherwise the all-ones vector is not orthogonal to our signed vector, and so it does not lie in the row space.


In summary if a connected graph is not bipartite, or bipartite with colour classes of equal size, the row space contains the all-ones vector. Otherwise it does not.


