# Every connected planar graph contains adjacent vertices with at most 2 common neighbors

I am looking for a reference for the following fact.

Let $G$ be simple undirected connected planar graph with $\geq 2$ vertices. Then $G$ contains an edge $\{u,v\}$ such that $|N(u) \cap N(v)| \leq 2$, in other words the number of common neighbors of $\{u,v\}$ is at most $2$.

Here's a sketch of the proof. Any edge incident on a vertex of degree $\leq 3$ satisfies this requirement. If there is a vertex $v$ of degree $4$ for which none of its edges satisfy the requirement, then $N[v]$ must be a $K_5$ which is not possible; if there is a vertex of degree 5 for which none of its edges satisfy then $N[v]$ must contain a $K_{3,3}$. Since any planar graph contains a vertex of degree $\leq 5$ this is sufficient.

I would like to be able to skip the proof in my paper, using a reference to known work instead. Can anyone give me a reference for the above fact?

-
Since your proof is only one paragraph, why not include it? "We will need the following lemma, which is likely well-known but for which we could not find a reference: Lemma: ... Proof: ..." Or, if you turn up a reference, "We will need the following lemma, first proved in [reference]: Lemma: ... Proof: ...". As a reader, I much prefer papers that are as self-contained as is possible without adding too much length. – Theo Johnson-Freyd Nov 18 '10 at 21:51
I agree with Theo Johnson-Freyd's sentiment that keeping a paper as self-contained as possible is best, particularly in a case where your sketch of the proof can be as short as you have stated. – sleepless in beantown Nov 18 '10 at 22:22
I was hoping not to have to give the proof; a sketch as short as the one above would not convince the target audience since it doesn't consist of mathematicians. But I guess I will just have to give a short proof in the appendix. – Bart Jansen Dec 13 '10 at 13:19

it is not what you are asking for (not a reference), but just maybe slightly easier proof, without searching for $K_{3,3}$. We may take any vertex $x$ of degree $d$, if any of $d$ vertices adjacent to $x$ has at least three neighbours between those $d$ vertices, we get at least $d+3d/2$ edges between $d+1$ vertices, hence $5d/2\leq 3(d+1)-6=3d-3$, $d\geq 6$. So degree of any vertex is not less then $6$, what is impossible.
By the way, we may even fix vertex $u$, and then find $v$. Indeed. if $v_1$, $v_2$, $\dots$, $v_d$ are labeled counterclockwise neighbours of $u$, then without loss of generality $v_i$ and $v_{i+1}$ are joined ($v_{d+1}=v_1$), and $u$ is outside the cycle $v_1-v_2-\dots-v_d$. But any triangulation of the (topological) polygon contains a vertex of degree 2.