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.

  • $\begingroup$ 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$. $\endgroup$ – pjs36 Apr 7 '15 at 22:03
  • $\begingroup$ 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$. $\endgroup$ – paw88789 Apr 7 '15 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$.

  • $\begingroup$ The three linear equations I came up with is x1+x3+x5=6, x3+1=x5, and x1+x3+x5=20. I know the last equation is wrong $\endgroup$ – Donald Dang Apr 7 '15 at 22:21
  • $\begingroup$ 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. $\endgroup$ – pjs36 Apr 7 '15 at 22:24
  • $\begingroup$ So would that mean that there are 1 handshakes for x1, 3 handshakes for x3, and 5 handshakes for x5, which all equal to 20? $\endgroup$ – Donald Dang Apr 7 '15 at 22:35
  • $\begingroup$ Exactly, the final equation will be $x_1 + 3x_3 + 5x_5 = 20$. $\endgroup$ – pjs36 Apr 7 '15 at 22:54

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.