The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
92 views

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$
in Graph Theory by Veteran (416k points)
edited by | 92 views
+1
Answer  will be 8

formulas used

Sum of degree$=2e$

by formula $r=e-v+2$
0
Ans is 8

1 Answer

+2 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.

by Boss (17.2k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,828 questions
54,735 answers
189,349 comments
80,095 users