Proof: Let $f, e, v$ denote the number of faces, edges, and vertices, respectively, in a planar graph. Use induction on $e$ to prove that $f = e−v + 2$ (this is known as Euler’s formula).
I think few similar questions were asked about this but I haven't seen one with induction on edges. I also have a different approach which I am curious if it is correct or not. There are two questions I have in mind
1: Do we use normal induction or strong induction ?
2: What kind of edge am I suppose to remove in the inductive step ?
My approach:
Let us assume a graph $G=(V,E)$ such that $|E(G)| = e, |V(G)| = v, |F(G)| = f$
Base case: Let $|E(G)|= 0$, then $v = 1$ and $f = 1$ (an isolated vertex). Then
$ 1 = 0 - 1 + 2 \Rightarrow 1 = 1$, therefore, claim holds for now
Let G have $|E(G)| = n, |V(G)| = v, |F(G)| = f$, and assume that inequality $ f = n-v+2$ holds for this graph.
To prove: prove that claim holds for $|E(T)| = n+1$,
Let us have $G' = (V',E')$ such that $|E(G')| = n+1, |V(G')| = v, |F(G')| = f$, There are two kind of edges we can remove, cover both by case distinction:
Case 1: An edge that creates extra two faces, remove this edge $e\in E(G')$, then one of the faces are lost, so we have $f-1 = (n+1)-1-v+2 \Rightarrow f = n-v+2$, so we are at $IH$ again, now add $e$ back to $G'$, we get $f = n+1-v+2$, which was assumed by IH, so the claim must hold.
Case 2: An edge that creates no extra faces, remove this edge $e'\in E(G')$ , then no faces are lost, so we have $f=n-v+2$, which is the $IH$, now add $e'$ back to G', so we get $f = n+1-v+2$ number of faces is not influenced as e does not contribute to any extra faces in G, so inequality must still hold.
Since base case has been proved, all cases were covered and it has been proved for $n+1$ then, claim must hold
I feel like this proof has a lot of gaps, please help me find them so that I can improve. Thank you
From what I can see, I believe that your proof is correct. As in the comments above, Euler's formula only holds for connected planar graphs. I'm going to present a slightly more rigorous version here, but the same idea applies.
Define a tree to be an acyclic connected graph. It is known that if it has $v$ vertices then it will have exactly $v-1$ edges. One can prove this by induction and this is shown here.
We now proceed by induction, where a tree of $v$ vertices is our base case. Applying Euler's formula yields : $V-E + F= v - (v-1) + 1 = 2$ which holds.
Now take any planar connected graph with $v$ vertices that is not a tree. It must contain a cycle, so we remove an edge in the cycle. This decreases the number of faces and number of edges by 1, so the value of $V - E + F$ doesn't change. We keep removing edges until we reach a tree, and we are done.