Skip to main content
3 of 3
removed capitals from title
YCor
  • 63.9k
  • 5
  • 187
  • 286

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

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?

batconjurer
  • 928
  • 4
  • 11