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

A planar graph has,

  • $\large\color{maroon}{\text{k}}$ connected components
  • $\large\color{maroon}{\text{v}}$ vertices
  • $\large\color{maroon}{\text{e}}$ edges

If the plane is divided into $\large\color{maroon}{\text{r}}$ regions then, what is the retation between $\large\color{maroon}{\text{k}}$ , $\large\color{maroon}{\text{v}}$ , $\large\color{maroon}{\text{e}}$ and $\large\color{maroon}{\text{r}}$ ?

asked in Graph Theory by Veteran (57.2k points) | 217 views
0
is planarity there in syllabus?

1 Answer

+1 vote
$(n-k)\leq e\leq \frac{(n-k)(n-k+1)}{2}$

Now we know $r=(n-k)$

$r\leq e\leq \frac{r(r+1)}{2}$
answered by Veteran (96.2k points)
+2

 srestha

I thought if something in this way,

$\begin{align*} &\text{r}_i = \text{No of finite closed region for component} \; i \\ &\text{Since each component } i \text{ is planar and connected} \\ &\Rightarrow r_i = e_i - v_i + 1 \;\;\; \left \{ \text{Euler formula for only closed region} \right \}\\ &\Rightarrow r = \sum r_i = \sum e_i - \sum v_i + \sum 1 \\ &\Rightarrow r = e - v + k \\ &\Rightarrow r = e - v + k + 1 \;\;\; \left \{ \text{considering outer region also} \right \} \\ \end{align*}$

0

 srestha

I thought if something in this way,

$$\begin{align*} &\text{r}_i = \text{No of finite closed region for component} \; i \\ &\text{Since each component } i \text{ is planar and connected} \\ &\Rightarrow r_i = e_i - v_i + 1 \;\;\; \left \{ \text{Euler formula for only closed region} \right \}\\ &\Rightarrow r = \sum r_i = \sum e_i - \sum v_i + \sum 1 \\ &\Rightarrow r = e - v + k \\ &\Rightarrow r = e - v + k + 1 \;\;\; \left \{ \text{considering outer region also} \right \} \\ \end{align*}$$

0
In any graph outer region could be maximum 1

all other are inner region, rt?

yes ur formula working well


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

39,815 questions
46,793 answers
140,929 comments
58,860 users