# We have a connected graph with $2n$ nodes. Prove that exist spanning subgraph each node with odd degree.

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?

• Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach? – Vincenzo Dec 25 '18 at 21:34
• @Vincenzo second one. – Aqua Dec 25 '18 at 21:35
• I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree. – Math1000 Dec 25 '18 at 22:06
• Take a look here. math.stackexchange.com/questions/3047513/… @Math1000 – Aqua Dec 25 '18 at 22:08
• If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={\bf 1}$ has a solution. I do not know if this makes things any easier. – Mike Earnest Dec 27 '18 at 17:44

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$$.