We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree.
Idea: Let $M$ be an adjacency matrix and work all over field $\mathbb{Z}_2$. Then if $M$ is nonsingular we know that equation $$M\vec{s} = (1,1,1,....1,1)$$ has notrivial solution. Suppose set $S$ has incidence vector $\vec{s}$. Then if for each node $a$ we color each edge in $N(a)\cap S$ we win.
There are quite a few questions here. First, where did I use conectivity, second, is it $M$ really nonsingular and do we even need that and last, if all this is true does this aproach actually work?
Note: I already asked initaly question and did get an answer, so please answer just this.
A base of the approach is any solution of the equation $M\vec{s} = (1,1,1,....1,1)$. But I don’t know how to show algebraically that it exists. In particular, it exists and unique provided the matrix $M$ is non-singular. Unfortunately, the adjacency matrix is singular for any graph which has two vertices with the same set of neighbors. For instance, for a cycle $C_4$ on four vertices. Also I remark that connectedness algebraically means that for each distinct indices $k,l$ there exists a power $M^k=\|m_{ij}\|$ such that $m_{i,j}>0$, but here we need to consider $M$ over $\Bbb Z$, but not over $\Bbb Z_2$.