I can't understand the proof of The Planar Separator Theorem
Any n-vertex planar graph has a 2/3-separator containing at most $\sqrt{8n}$ vertices.
Proof of the theorem 10 Graph Separators
Let's go through the proof.
Let $G$ be an embedded planar graph with $n \geq 3$ vertices, and let $k = \sqrt{2n}$ Without loss of generality, we can assume that $G$ has no loops or parallel edges, and that every face is a triangle bounded by three distinct edges. For any simple cycle $C$ in G, let $In(C)$ and $Out(C)$ denote the vertices inside and outside $C$,r respectively. No vertex of $In(C)$ is adjacent to any vertex of $Out(C)$. Let $C$ be a simple cycle satisfying three conditions:
$C$ has at most $2k$ vertices.
$|Out(C)| < 2n/3$.
Subject to conditions 1 and 2, the difference |In(C)| and |Out(C)| is as small as possible.
Let D be the subgraph of G in the closed interior of C. For any two vertices $u$ and $v$ in $C$, let $c(u, v)$ denote their distance in $C$, and let $d(u, v)$ denote their distance in $d$.
Claim 1. $d(u, v) = c(u, v)$ for all vertices $u$ and $v$ in $C$.
We clearly have $d(u, v) \leq c(u, v)$ for all $u$ and $v$, because $C$ is a subgraph of $D$. Suppose there are distinct vertices $u$ and $v$ such that $d(u, v) < c(u, v)$ choose such a pair so that $d(u, v)$ is minimized. Let be a shortest path from $u$ to $v$ in D. If contained any other vertex $w$ in C, then $d(u, w) + d(w, v) = d(u, v) < c(u, v) \leq c(u, w) + c(w, v)$, so either $d(u, w) < c(u, w)$ or $d(w, v) < c(w, v)$ either possibility contradicts our choice of $u$ and $v$.
How this is possible, take a look a at the picture. It's obviously that path in $D$ is shorter than path in $C$. The part with additional vertex $w$ wasn't understood at all, at the end we get contradiction of choice of $u$ and $v$.
Claim 2. $C$ has exactly $2k$ vertices.
I can't get it too, because the proof is based on Claim 1.
Please, can you shed light on the proof.
Thanks!
Addendum:
- We have 3 conditions that $C$ should satisfy
- For purposes of deriving a contradiction, we have assumption $|In(C)| \geq 2n/3$
- We choice $w$ and $v$ such that $d(u,v)$ is minimized and show that either $d(u, w) < c(u, w)$ or $d(w, v) < c(w, v)$; either possibility contradicts our choice of $u$ and $v$. But this is completely fine with minimized $d(u,w)$, what is the contradiction?
- It turns out that we can find a better separation $C^{+}$, which is satisfies (1.1) and (1.2)(with assumption that 2 is true, which is already mistaken), but don't satisfy (1.3), and conclusion that claim is true. But how come, what about the contradiction of our choice of $u$ and $v$?
Sorry, it's not complication in terms of mathematics, but it's really mixed up in terms of logic.