2
$\begingroup$

I'm doing a question in my text that asks me to find how many regions a graph has if it has 6 vertices all of which has degree 4. I know i'm supposed to use the euler theorem of $r=e-v+2$, but to use this I need to find the number of edges first. So how do I find the number of edges in a graph if I know how many vertices there are and their degrees?

$\endgroup$
  • $\begingroup$ See Handshaking Lemma and the degree sum formula (naming of these varies among authors). $\endgroup$ – hardmath Feb 16 '17 at 2:07
  • 1
    $\begingroup$ Note that the notion "regions a graph has" is meaningful only for planar graphs. $\endgroup$ – hardmath Feb 16 '17 at 2:13
4
$\begingroup$

The sum of the vertex degree values is twice the number of edges, because each of the edges has been counted from both ends.

In your case $6$ vertices of degree $4$ mean there are $(6\times 4) / 2 = 12$ edges.

$\endgroup$
  • $\begingroup$ ...and without giving too much away, there is only one simple graph that has $6$ vertices all of degree $4$, and it corresponds to one of the regular polyhedra. $\endgroup$ – Joffan Feb 15 '17 at 16:59

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.