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$
2
  • $\begingroup$ See Handshaking Lemma and the degree sum formula (naming of these varies among authors). $\endgroup$
    – hardmath
    Commented Feb 16, 2017 at 2:07
  • 2
    $\begingroup$ Note that the notion "regions a graph has" is meaningful only for planar graphs. $\endgroup$
    – hardmath
    Commented Feb 16, 2017 at 2:13

1 Answer 1

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$
1
  • $\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
    Commented Feb 15, 2017 at 16:59

You must log in to answer this question.

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