A 4-regular planar graph $G$ has $117$ vertices. How many faces does $G$ have?

**
Details and assumptions
**

A graph is
**
$k$
-regular
**
if each vertex has a degree of
$k$
.

A
**
planar graph
**
can be embedded in the plane, where edges intersect only at their endpoints.

The answer is 119.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Can you generalize this to $4$ -regular graphs with different numbers of vertices?

Are we given that the $G$ is connected? Otherwise we could have several disconnected components that are each $4$ -regular, which would yield a different answer.

Jimmy Kariznov
- 7 years, 10 months ago

I believe that I would be able to generalize this to $k$ -regular graphs with $v$ vertices. The number of edges should be $\frac{kv}{2}$ in general, since each vertex must be connected to $k$ other vertices, and we divide by $2$ so we don't count each edge twice. If we want to generalize the number of faces, we can use Euler's formula, getting $v-\frac{kv}{2}+f=2$ , so $f=2+\frac{v(k-2)}{2}$ .

Raymond Lin
- 7 years, 10 months ago

4-regular graphs have $e = 2v$ , thus $f = v + 2$ .

Michael Tong
- 7 years, 10 months ago

The answer is correct, but I was a bit hesitant as to what constitutes a face. I wasn't sure if the unbounded region outside the graph counts as a face. Maybe add a note to the problem?

C Lim
- 7 years, 10 months ago

Log in to reply

Yes, I believe that, by convention, the unbounded area outside the graph counts as a face. I referenced the following for this information: http://www.cs.uiuc.edu/~mfleck/building-blocks/version-1.0/planargraphs.pdf

Raymond Lin
- 7 years, 10 months ago

Nice Solution! I did the same.

Anindya Sharma
- 7 years, 9 months ago

5 Helpful
0 Interesting
0 Brilliant
0 Confused

To calculate the number of faces, we will use Euler's formula, for a 2D plane: $F+V-E = 2$ .

As G is 4-regular, each vertex is connected to 4 others, for a total of $4 \times 117 = 468$ connections.

However this will count every edge twice (ie. Point A - Point B as well as Point B - Point A), so the total number of edges is:

$E = \frac{468} {2} = 234$

Using Euler's formula with $V=117$ , $E=234$ , we find:

$F+V-E = 2$

$F = 2+E-V$

$F = 2+234-117$

$F = 119$

2 Helpful
0 Interesting
0 Brilliant
0 Confused

According to the degree sum formula: $\Sigma deg(v)=2e$ , so $e=\frac{4*117}{2}=234$ .

According to Euler's formula: $v - e + f = 2$ , so $f=2+e-v=119$

2 Helpful
0 Interesting
0 Brilliant
0 Confused

According to Euler's Formula V - E + F = 2 where

V = number of vertices

E = number of edges

F = number of faces

We are given the number of vertices so we only need to calculate the number of edges to solve for F.

By the Handshaking lemma ( you need two person for every handshake ) Every 2 degree contributes to 1 extra edge.

So the number of edges in the graph = total degree/2

Since we know that the graph is a 4 regular graph, all vertices has degree four (means four edges coming out of every vertices)

So, total degree = 4 * 117 = 468

Number of edges = 468/2 = 234

By Euler's Formula 117 - 234 + F = 2

Shifting things around...

F = 119

1 Helpful
0 Interesting
0 Brilliant
0 Confused

1 Helpful
0 Interesting
0 Brilliant
0 Confused

Euler's formula for planar graphs states that:

$v-e+f=2$

Where v = # of vertices, e = # of edges, f = # of faces.

We know v = 117, so we just need to find e.

Since the graph is 4-regular, each vertices has 4 edges connected to it. So it can be just a 117-gon with every adjacent vertices and every other vertices connected. The number of edges is then 117*2.

Plug this back into $v-e+f=2 \Rightarrow f = e+2-v \Rightarrow f = 2*117-117+2 = 117+2 = 119$

So 119 is the answer.

1 Helpful
0 Interesting
0 Brilliant
0 Confused

We use Euler's Polyhedral Formula: V-E+F=2, where V = #vertices, E = #edges and F = #faces.

Since each vertex is of degree 4, the total number of edges is clearly (4
*
117)/2=2
*
117=234. We know V = 117. Hence F=2+E-f=2+234-117=2+117=119.

0 Helpful
0 Interesting
0 Brilliant
0 Confused

Since Euler's Degree Sum Formula implies that for any $k-regular$ graph with $V$ vertices then there are $\frac{k*V}{2}$ edges.

Therefore, there must be $234$ edges present.

Using Euler's Formula, we have $V-E+F=2$ where $V,E,F$ are the number of vertices, edges and faces respectively.

This gives $F=117+2 = 119$ so there are $119$ faces.

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

0 Helpful
0 Interesting
0 Brilliant
0 Confused

We use a simple rule to generate $4$ -regular planar graph $G_{k}$ with $n$ vertices, where $n$ is of the form : $6 + 3*k$ .

$G_{0}$
is the
the graph of the octahedron
. It has
$6$
vertices and
$8$
faces (
**
we also include the infinite face
**
).

The outer triangle is oriented upwards.

$G_{k, k \geq 1}$ is obtained by:

- remove the $3$ outer edges of $G_{k-1}$ and obtain $G^{*}_{k-1}$
- put $G^{*}_{k-1}$ inside a triangle that has an opposite orientation than the outer triangle of $G_{k-1}$
- for every vertex of this new triangle, construct $2$ edges that will link the vertex to the $2$ nearest vertices of $G^{*}_{k-1}$

This procedure adds $3$ vertices and $3$ inner faces for every increment of $k$ . So for every vertex, we get one additional face.

It follows that $G_{117}$ has :

$f = 8 + (117-6) = 119$ faces.

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

There are $\frac{117*4}{2}=234$ edges in $G$ , since each vertex must be connected to $4$ other vertices, and each edge connects $2$ vertices (if we didn't divide by $2$ , we would count each edge twice).

By Euler's formula, $v-e+f=2$ , where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces. We plug in our values for $v$ and $e$ , and solving for $f$ , we get our answer to be $\fbox{119}$ .