edited by
8,426 views
7 votes
7 votes

Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?

  1. $6$
  2. $8$
  3. $12$
  4. $20$
edited by

1 Answer

3 votes
3 votes

Method 1 (brute force) :-

Method 2 :-

We know that,

sum of degree of vertices = 2 * number of edges (handshaking theorem)

$\implies 4+4+4+4+4+4 = 2 * e$

$\implies e = 12$

Also according to Euler's formula,

$r=e-v+2$

$\implies r= 12 -6 +2 $

$\implies r= 12 -6 +2 $

$\implies r= 8$

$\therefore$ Option $2.$ is correct.

edited by
Answer:

Related questions

3 votes
3 votes
2 answers
1
Arjun asked Jul 2, 2019
2,066 views
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ?$m\neq n,\ \ m,n \geq 2$$m\neq n,\ \ m,n \geq 3$$m=n,\ \ m,n \geq ...
4 votes
4 votes
3 answers
3
go_editor asked Jul 8, 2016
4,161 views
$G_1$ and $G_2$ are two graphs as shown:Both $G_1$ and $G_2$ are planar graphsBoth $G_1$ and $G_2$ are not planar graphs$G_1$ is planar and $G_2$ is not planar$G_1$ is no...