# Determining the number of vertices of each degree

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.

• You've reversed something: They say "the number of vertices of degree $3$ is one more than the number of vertices of degree $5$", so a single vertex of degree $3$ would lead to $0$ vertices of degree $5$. Apr 7, 2015 at 22:03
• I don't think it's possible. It seems like you'd want two vertices of degree $5$, three of degree $3$, and one of degree $1$. But both vertices of degree $5$ would have to have an edge to all other vertices. But then there is no vertex of degree $1$. Apr 7, 2015 at 22:09

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$.
• The first two are indeed good. The last should take into account what each vertex of degree $k$ is contributing to the number of handshakes; so if we have $x_3$ vertices of degree $3$, say, then each contributes $3$ handshakes, for a total of $3x_3$ from the vertices of degree $3$; just "weight" the last equation, and it'll be right. Apr 7, 2015 at 22:24
• Exactly, the final equation will be $x_1 + 3x_3 + 5x_5 = 20$. Apr 7, 2015 at 22:54