Hey guys need help with this question. "A graph has 33 edges, and every vertex has degree 7 or degree 8. How many vertices does the graph have?".

Any help would be much appreciated.

Printable View

- Jun 18th 2010, 10:47 PMjvignacioVertices help
Hey guys need help with this question. "A graph has 33 edges, and every vertex has degree 7 or degree 8. How many vertices does the graph have?".

Any help would be much appreciated. - Jun 18th 2010, 11:17 PMProve It
From the handshaking lemma

$\displaystyle \sum{\textrm{deg}\,(v)} = 2|E|$

Since there are $\displaystyle 33$ edges, that means $\displaystyle \sum{\textrm{deg}\,(v)} = 66$.

That means that $\displaystyle 7m + 8n = 66$, where $\displaystyle m$ is the number of vertices with degree $\displaystyle 7$ and $\displaystyle n$ is the number of vertices with degree $\displaystyle 8$.

By inspection, $\displaystyle m = 6$ and $\displaystyle n = 3$.

So there are $\displaystyle 9$ vertices. - Jun 18th 2010, 11:26 PMjvignacio