I am trying to prove some graph theory and wonder if I did this correctly?

Question: There are graphs with in total 5 vertices. Further, each vertex is connected (with one edge) to an odd number of other vertices but not to an even number of other vertices. true or false?

Answer: i said false and the proof: it is impossible to draw that because if we have 5 vertices and every vertex is connected with an edge to an odd amount of other vertices and no even amount of vertices, which can't be true because the even vertices must connect to an even amount of vertices, all vertices can't be odd.

Is my answer correct?


Your answer is correct though maybe it could be more mathematical. I sugest the following:

Label the vertices $\{1,2,3,4,5\}$. Say that vertex $i$ has $p_i$ number of adjacent vertices. As $p_i$ is odd, for each $i\in \{1,2,3,4,5\}$ we know that $p_i=2q_i+1$ for some number $q_i$. Thus the total degree of all verices in the graph is:

$$D=\sum_{i=1}^5 p_i = p_1+p_2+p_3+p_4+p_5 = 2(q_1+q_2+q_3+q_4+q_5)+5.$$

However each edge is connected to two vertices. Thus each edge will add an even number to the total degree, i.e. the number $D$ needs to be even. Thus we have a contradiction, as we have concluded that $D$ is odd.

The question may be generalized, and the general result is that if you have an odd number of vertices in a graph, then they may not all have an odd number of neighbours.


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.