Register

UGC NET CSE | June 2019 | Part 2 | Question: 4

• edited by
10,377 views
8 8 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$

1 Answer

3 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
Voting & Accepting an answer helps improve the community
Answer:
← Previous · UGC NET CSE | June 2...Next → · UGC NET CSE | June 2...
← Previous in category · UGC NET CSE | June 2...Next in category → · CMI2018-B-5
Position:
Show:

Related questions

3 3 votes
2 2 answers
2.8k
2.8k views
Arjun asked Jul 2, 2019
2,770 views
UGC NET CSE | June 2019 | Part 2 | Question: 5
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 ...
1 1 vote
1 1 answer
1.9k
1.9k views
Arjun asked Jul 2, 2019
1,865 views
UGC NET CSE | June 2019 | Part 2 | Question: 69
Consider the following properties with respect to a flow network $G=(V,E)$ in which a flow is a real-valued function $f:V \times V \rightarrow R$:$P_1$: For all $u, v, \i...
4 4 votes
3 answers 3 answers
5.6k
5.6k views
go_editor asked Jul 8, 2016
5,640 views
UGC NET CSE | June 2012 | Part 3 | Question: 72
$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...
10 10 votes
3 answers 3 answers
9.5k
9.5k views
Arjun asked Jul 2, 2019
9,463 views
UGC NET CSE | June 2019 | Part 2 | Question: 1
Consider the poset $( \{3,5,9,15,24,45 \}, \mid).$Which of the following is correct for the given poset ?There exist a greatest element and a least elementThere exist a ...