I know that all trees are planar, and so now I'm wondering whether 2-connected graphs are necessarily planar. I would imagine that this is true given that all 2-connected graphs have an ear decomposition (Theorem 4.10 in [1]), and that every ear decomposition I have seen is planar, like the following example (Figure 4.3, from [1]):
So to be sure, I naturally tried to prove that ear decompositions are planar, but I'm uneasy about my proof:
Proof. Let $G$ be a 2-connected graph with an ear decomposition $E = G_0, G_1, \ldots, G_k$, where $G_0$ is a cycle and $G_i$ are ears for $1 \leq i \leq k$. We proceed by induction on the number of ears, with the base case being $k = 1$ ($E = G_0, G_1$), which is obviously* planar. So, we assume the statement is true for any graph with an ear decomposition having $k - 1$ ears, and we let $G$ have $k$ ears. Let $P = G_k\setminus \{u, v\}$, where $G_k$ is the "outer" ear of $G$ and $u, v$ are the end-vertices of $G_k$, and note that $G - P$ is planar by the induction hypothesis. $(G - P) + P$ is clearly* still planar, so $G$ is planar. $\blacksquare$
In particular, I'm uneasy about two aspects:
- Are the jumps in logic that I made at the asterisks okay? How could they be stated better?
- Am I characterizing ear decompositions correctly?
This is all. Thank you in advance for any advice!
References
1: Graphs and Digraphs, (7 ed.).
No. For any fixed $k\geq 1$, let $n\gg k$, let $F,H$ be two copies of a complete graph on $n$ vertices. Identify a copy of $K_k$ in $F$ and another one in $H$, and merge then together, akin to a $k$-clique-sum keeping all edges.
The graph has connectivity exactly $k$ and is non planar.
e.g. with $n=5,k=2$, the following graph is $2$-connected, not $3$-connected, and non-planar because it contains $K_5$.
The issue with your proof is that "outer" is not defined if the graph is non-planar.