Graph Theory proof: Let G be a planar graph that doesn't contain K3...

Question

So I'm trying to solve this practice exam question,

Let $G$ be a planar graph with at least two edges and does not contain $K_{3}$ as a subgraph. Prove that $|E|\leq 2|V|-4$.

Now I started doing this by induction, but it seems to me like the base-case is a counter-example. If I draw two edges that connect two vertices, this seems to be planar since the edges don't intersect and it doesn't contain $K_{3}$ because it only has two nodes. Yet in this case, $2\not\leq 2(2)-4$.

Am I doing something wrong? The edges don't have to be straight do they? I thought the shape of the edges was unimportant.

Answer 1

This is pretty standard, just combine the Euler formula with counting edges by faces.

By Euler formula

$$V-E+F=2$$

The proof below, assumes that there exists at least two faces, you need to check separately the case $F=1$.

Now, lets count the edges by faces. Since each edge belongs to exactly 2 faces (here is where we need $F \geq 2$) our count is exactly $2E$.

The graph has $F=E-V+2$ faces, and each face has at least $4$ edges (because no triangles), out count is at least $$4F=4(E-V+2) \,.$$

Therefore $$2E =\mbox{our count} \geq 4E-4V+8 \,.$$

This is exactly your inequality.

P.S. The proof assumes that the graph is simple, if the graph is not simple then loops lead to faces with only one edge and multiedges to faces with 2 edges.

Answer 2

We first prove the following lemma.

If $G$ is a connected simple graph, $|E(G)| \geq 2$. Then, every region of has length at least $3$.

Proof. Indeed, the only possible nontrivial closed walk of length at most $2$ in a simple graph traces a single edge in both directions. Such a walk can form a boundary of a region only if the whole graph consists of $2$ vertices and $1$ edge, proving the lemma.

Now, we want to show that given a planar graph $G$ with $|E(G)| \geq 2$ which does not contain $K_3$ as a subgraph, we have $|E(G)| \leq 2|V(G)| - 4$.

We may assume that $G$ is connected by adding an extra edge. Note that if we do not make any assumption on whether $G$ contains $K_3$ or not, we have the relation $$2|E(G)| = \sum_{\text{regions $r$}} \mathrm{Length}(r) \geq 3\mathrm{Reg}(G)$$ by the Lemma, so that $\mathrm{Reg}(G) \leq \tfrac{2}{3}|E(G)|$. By Euler, we also have $$2 = |V(G)| - |E(G)| + \mathrm{Reg}(G) \leq |V(G)| - \frac{|E(G)|}{3}.$$

Hence, $6 \leq 3|V(G)| - |E(G)|$. Now, if $K_3 < G$, then $G$ has not region of length $3$, so we have that $\tfrac{1}{2}|E(G)| \geq \mathrm{Reg}(G)$. It follows that $|E(G)| \leq 2|V(G)| - 4$, as desired.