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.

  • $\begingroup$ Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach? $\endgroup$ – Vincenzo Dec 25 '18 at 21:34
  • $\begingroup$ @Vincenzo second one. $\endgroup$ – Aqua Dec 25 '18 at 21:35
  • $\begingroup$ 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. $\endgroup$ – Math1000 Dec 25 '18 at 22:06
  • $\begingroup$ Take a look here. math.stackexchange.com/questions/3047513/… @Math1000 $\endgroup$ – Aqua Dec 25 '18 at 22:08
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ Anyway, do you have a perhaps an idea how to atack this algebraicly $\endgroup$ – Aqua Dec 25 '18 at 22:00
  • $\begingroup$ You think this is hopless try with linear algebra? $\endgroup$ – Aqua Dec 26 '18 at 22:01
  • $\begingroup$ @greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally. $\endgroup$ – Alex Ravsky Dec 30 '18 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.