in Graph Theory
521 views
2 votes
2 votes

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}}$ ?

in Graph Theory
by
521 views

1 comment

is planarity there in syllabus?
0
0

1 Answer

1 vote
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}$

3 Comments

 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*}$

2
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
0
In any graph outer region could be maximum 1

all other are inner region, rt?

yes ur formula working well
0
0