# Vertices help

• Jun 18th 2010, 10:47 PM
jvignacio
Vertices 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 PM
Prove 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 PM
jvignacio
Quote:

Originally Posted by Prove 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.