# Proof Verification: In a graph on five vertices, can every vertex have odd degree?

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.

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.