Question: Let G be a simple graph with 6 vertices and 10 edges such that every vertex of G has an odd degree. If the number of vertices of degree 3 is one more that the number of vertices of degree 5, how many vertices of each degree does G have?
I don't seem to have anything in my notes, but my thought process right now is that if we have a vertex of degree 3 I must have 2 vertices of degree 5, which sum up to 13. Since I'm given the edges, and according to the handshake lemma it needs to equal to 20. Where do I go from here.
Best Answer
Let $x_1, x_3,$ and $x_5$ be the number of vertices of degrees $1, 3$, and $5$, respectively.
Since the graph has $6$ vertices, you get a linear equation involving $x_1, x_2,$ and $x_3$. Since there's one more vertex of degree $3$ than there is of degree $5$, you'll get another linear equation. Finally, by the "handshake" lemma you mentioned, we get one more linear equation. I'm confident that you can come up with these equations, but just ask for more details.
If you can set up those equations, you'll have $3$ equations in $3$ unknowns; if you get a(ny) solution(s) and they "makes sense" here (eg, non-negative integers only, each $x_i$ is between $0$ and $6$, etc) you've found the possibilities for $x_1, x_2$, and $x_3$.