0
$\begingroup$

Using Euler's formula in graph theory where

$r - e + v = 2$

I can simply do induction on the edges where the base case is a single edge and the result will be 2 vertices. A single edge also has only one region which is the external region.

$r - 1 + v = 2$

$1 - 1 + v = 2$

$v = 2$

Which is true if I drew a connected graph of that has a single edge there are two vertices. However, the inductive step where I am supposed to prove that there are $e + 1$ edges I am confused on how to prove this. I can simply add another edge and the formula will still stand true but I don't think that's the correct way to do it. For example, I don't think my professor would accept this on the exam if I tried doing the inductive step like this:

$r - e + v = 2$

$1 - (e + 1) + v = 2$

if we let $e=1$ again then there would be

$1 - 2 + v = 2$

$v = 3$

which is true, a connected graph of two edges has 3 vertices at most. However, i do not think this is the correct way to prove Euler's formula during the inductive step.

$\endgroup$
  • 1
    $\begingroup$ You also have to consider the number of faces. $\endgroup$ – Peter Mar 18 at 9:52
  • $\begingroup$ Well if we have at most 2 edges there is only one face and that is the external region, but if I remember correctly there should be a formula that correlates the amount of faces to edges. For larger numbers, I could simply plug in that formula into Euler's and then solve. But that might be excessive... $\endgroup$ – Code4life Mar 18 at 9:55
  • 1
    $\begingroup$ See Euler characteristic for Plane graphs : the base case is $2$ faces, that needs $3$ vert and $3$ edges. Thus : $v-e+f=3-3+2=2$. $\endgroup$ – Mauro ALLEGRANZA Mar 18 at 9:59
  • 1
    $\begingroup$ Then to close the induction, you have to prove that any change to the graph that creates an additional face while keeping the graph planar does not change to number. $\endgroup$ – Mauro ALLEGRANZA Mar 18 at 10:00
  • $\begingroup$ So I should do the induction on the number of faces rather than the number of vertices or edges? Should I just do $r+1$ in Euler's formula? How would I go about doing the inductive step then? $\endgroup$ – Code4life Mar 18 at 11:10
1
$\begingroup$

Let $v$ be the number of vertices, $e$ the number of edges and $r$ the number of regions in a connected simple planar graph $G$. To prove Euler's formula $v - e + r = 2$ by induction on the number of edges $e$, we can start with the base case: $e = 0$. Then because $G$ is connected, it has a single vertex, so we have $1 - 0 + 1 = 2$ and formula holds.

Now suppose the formula holds for all graphs with no more than $e - 1$ edges. Let $G$ be a graph with $e$ edges. Consider two cases. Case 1: G does not contain a cycle. Then G is a tree, for example

Example of a tree on 6 vertices

It has only $r = 1$ region and because it is connected, it has $v - 1$ edges, so we have $v - (v - 1) + 1 = 2$ and formula holds.

Case 2: G contains at least one cycle $C$. Remove an edge $p$ from the cycle $C$ to get a path $P$, for example:

Example of cycle and a path on 5 vertices

Cycle $C$ separates the plane in two regions. When we remove the edge $p$ from $G$, we create a new graph $G'$, where we merge these two regions. So $G'$ has by construction one less region than $G$ $$r' = r - 1,$$ the same number of vertices $v'=v$ and one less edge than $G$ $$e' = e - 1,$$ so induction hypothesis holds and we have $$ v - (e - 1) + (r - 1) = 2 $$ and from this also $$ v - e + r = 2, $$ what we needed to prove. More about Euler's formula is here. Formula can easily be generalized for disconnected graphs or graphs with loops or parallel edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.