Characterizing graphs whose incidence matrix has the all ones vector in its row span

Question

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?

Answer 1

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.

Answer 2

No, this is not true. Let $G$ be the bowtie graph (this is the graph obtained by gluing two triangles at a vertex $u$). Then, $G$ does not have a spanning regular subgraph, but $\mathbb{1}$ is in the row space of $G$. Just set $x_e=\frac{1}{4}$ if $e$ is adjacent to $u$ and $x_e=\frac{3}{4}$ for the other two edges.

The exact characterization of when $\mathbb{1}$ is in the row space of $G$ can be extracted from Chris Godsil's answer.

Characterization. $\mathbb{1}$ is in the row space of $G$ if and only if each bipartite component of $G$ is balanced (the left and right sides have the same number of vertices).