Question

I am looking for a reference for the following fact. Let G be an undirected, simple, connected planar graph on at least 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?

Answer 1

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.