0
$\begingroup$

can you check my soultion?

Task:In graph G every two vertices have odd number of common neighbors. Prove that every vertex has even degree.

My thinking. I choose arbitrary vertex $v$ and build subgraph, which contain this vertex and all his neighbors. Every neighbor has even degree (odd common neighbors plus chosen vertex). But in every graph (subgraph) sum of degrees is even,so vertex $v$ has to have even degree. That ends the proof. Is it correct?

$\endgroup$
  • $\begingroup$ Firstly, the degree of vertices in a subgraph can be different from the degree of vertices in the original graph. Secondly, when you say "odd common neighbors plus chosen vertex", the chosen vertex is also among the set of common neighbors, so you cannot count it again! $\endgroup$ – M. Vinay Jun 2 '16 at 8:50
  • $\begingroup$ But here I am looking at degree of only vertex v and I picked him and all his neighbors. So he has to have the same degree in subgraph and in graph G. Lets assume I have triangle abc. For ab the only common neighbor is c. Isn't ? So in subgraph: number of common neighbor for v and his neighbor is odd, so degree of this neighbor is even. Or not? $\endgroup$ – MrFrodo Jun 2 '16 at 10:39
  • $\begingroup$ Yes, $v$ will retain its original degree in the subgraph as well. But the degrees of the neighbors of $v$ will be different. They may have neighbors outside the subgraph (somewhere else in the graph). $\endgroup$ – M. Vinay Jun 2 '16 at 10:46
  • $\begingroup$ You say: "In the subgraph, the number of common neighbors of $v$ and its neighbor is odd, so the degree of this neighbor is odd". Yes, but only inside the subgraph. The total degree of the neighbor might be larger than this. For example, it might have one neighbor outside that subgraph. In the example of a triangle $abc$, $a$ and $b$ have a common neighbor $c$. So $c$ has degree $2$ in the subgraph $abc$. But maybe $c$ is adjacent to some other vertex $d$ in the original graph. Your argument does not consider this possibility. $\endgroup$ – M. Vinay Jun 2 '16 at 10:49
  • $\begingroup$ Yes, you are right. Has the every neighbor in subgraph even degree? If so, vertex v also has, but v is arbitrary, so every vertex in graph has even degree. $\endgroup$ – MrFrodo Jun 2 '16 at 10:52

Your Answer

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

Browse other questions tagged or ask your own question.