Correct non-inductive proof of Euler's Formula $|V|+|F|-|E|=2$?

Question

Theorem: The number of vertices $|V|$, edges $|E|$, and faces $|F|$ in an arbitrary connected planar graph are related by the formula $$|V|+|F|-|E|=2$$

Proof Attempt:

(For acyclic planar graphs) Let $G(V,E)$ be an acyclic graph. For any line-subgraph $L=(V',E')$ of $G$, we can easily verify that $|V'|=2$, $|E'|=1$, and $|F'|=1$ where $F'$ is the face of a line graph. Thus, $|V'|+|F'|-|E'|=2$. As we construct $G$ from $L$ by adding edges, note that for each edge we add, we add a vertex so for any number of edges $n\in\Bbb{N}$ we add, we also add $n$ vertices. Hence, $(|V'|+n)+|F'|-(|E'|+n)=|V|+|F|-|E|=2$.

(For planar graphs with cyclic subgraphs) The smallest planar graph with a cyclic subgraph is $C_3$(a triangle). Clearly, any planar graph with a cyclic subgraph can be constructed by adding more points and edges to $C_3$. We assert that to add an edge to $C_3$, we either

1. Add a point $v^*$ on an existing edge $l$ which 'splits' $l$ to two different edges then connect $v^*$ to an existing vertex with a new edge; this adds 2 edges, 1 vertex, and 1 face or

2. Connect two existing vertices, not connected by an edge, with a new edge; this adds a face or

3. Add 2 new vertices with each of them on an existing edge, then connect the two new vertices with a new edge; this adds 2 vertices, 1 face, and 3 edges.

Nevertheless, observe that method (1) and (3) above is a sequential combination of two very primitive steps:

• Add a vertex to an existing edge.

• Connect two existing vertices, not connected by an edge, with a new edge. (This is method (2) above.)

Note:

• Adding a point to an existing edge implies $|V|+1$, $|E|+1$, and $|F|+0$.
• Method 2 implies $|V|+0$, $|E|+1$, and $|F|+1$.
• Adding a point outside any edge forces us to connect this new vertex with an existing vertex by a new edge; this implies $|V|+1$, $|E|+1$, and $|F|+0$.

Hence, the form of numerical parameter variations occurring every time we construct a new connected planar graph is of the following:

• $(|V|+n)+|F|-(|E|+n)$
• $|V|+(|F|+m)-(|E|+m)$

Therefore, $|V|+|F|-|E|=2$.

Answer 1

Your proof is not a non-inductive proof. The steps where you construct $G$ from a smaller graph by adding edges, and check that $|V|-|E|+|F|=2$ still holds because the left-hand side does not change, are the inductive steps of your proof.

This is fine! Induction is great. But you are falling into the classic "induction trap" that everyone falls into when writing induction proofs about graphs.

Whenever you write an inductive step that "goes up", starting with a graph for which your result holds and making it bigger, you set yourself the goal of showing that every graph can be obtained by growing your base case in this way. You are not careful about this:

• In the cyclic case, you write "Clearly, any planar graph with a cyclic subgraph can be constructed by adding more points and edges to $C_3$". This should set off alarm bells. Whenever you are justifying an intuitively clear statement with "clearly", you haven't written a proof.
• In the acyclic case, you haven't even stated the claim that your proof needs to work: that every tree can be built by repeatedly adding leaves to a line-graph. (Do you mean a path graph? A line graph is something else.)

We can avoid the problem of proving these hard-to-prove statements by writing an inductive step that "goes down" instead. Here, we assume that the result holds for all small graphs, and take a slightly larger graph; then, delete a vertex or edge from it, reducing it to a graph that your inductive hypothesis applies to.

For example, when proving Euler's formula for acyclic graphs, you could first argue (in your favorite way) that any such graph contains a vertex of degree $1$, then delete that vertex together with the edge out of it. This reduces the graph to a smaller one for which you have already verified Euler's formula.

Here, there is no worry that we've gotten all of the graphs we're considering in this case, because we started with an arbitrary such graph.

Aside from this, your strategy looks good. You should just rethink your arguments in terms of removing an edge or vertex, rather than adding them.