How to prove this question using induction?

Question

The question is: Prove that if graph $G$ is a Connected Planar Graph where each region is made up of at least $k\,(k\ge3)$ edges, then it must satisfy:

$e\ge\frac{k(v-2)}{k-2}$

$e$ means $G$'s number of edges, $v$ means $G$'s number of vertices

Then I am prepare using induction to prove this.But I don't know which variable should I use. The number of edges or the number of vertices? And I even don't know what $k$ means here. Is $k$ a number no less than $3$ or it equals to the minimum number of edges of $G$'s regions? Due to these doubts,I am confused how to start my induction correctly.

Answer 1

Generally, when you're using induction to prove a fact about relationship between a dependent variable and an independent variable, the induction is on the independent variable. Another generalization is that if you're proving an inequality, the induction is likely on the "less than" side. The expression $\frac {k(v-2)}{k-2}$ is written as if it's a function of $v$, making $v$ the indepedent variable. Furthermore, it it more common for the number of edges to be considered a dependent variable with respect to the number of vertices, than the reverse. None of this is iron clad rules, and having not worked out the proof myself, I can't say for certain, but I would strongly expect the induction to not be on $e$; I would expect it be on either $v$ or on the number of regions.

As for $k$, it is an integer that is greater than $2$, and it is a lower bound for the number of edges for each region. It is not necessarily the minimum; there is a difference between "minimum" and "lower bound". Lower bound for a set of values means that the values are never lower, while minimum means they are never lower, and at least one value is equal. So, for instance, I'm confident that 10 is a lower bound for the age of Fortune 500 CEOs, but it's not the minimum age, because no such CEO is actually 10.

Answer 2

It is no necessary to use induction.To resolve it,we need to use Euler's Formula:

For a simple Connected Planar Graph G in which $e$,$v$,$f$ means its number of edges, verticesit,and regions,G must satisfy $v-e+f=2$.

And we also need:

For a simple Connected Planar Graph G,its sum of the number of edges of all regions is equal to twice the number of its edges.

We can supposed that the graph has $f$ regions.Since each region's edges is not less than $k$,the sum of the number of edges of all regions is not less than $kf$.In other words,

$2e\ge kf$

Then using Euler's Formula,we have:

$2e \ge k(2+e-v)\implies (2-k)e \ge k(2-v) \implies e \ge \frac{k(v-2)}{k-2}$

Then question resolved.