0
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2015 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, 2015 at 22:09

1 Answer 1

Reset to default
2
$\begingroup$

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$.

$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 at 22:35
  • $\begingroup$ Exactly, the final equation will be $x_1 + 3x_3 + 5x_5 = 20$. $\endgroup$
    – pjs36
    Apr 7, 2015 at 22:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .