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?

  • 5
    $\begingroup$ 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. $\endgroup$ – Theo Johnson-Freyd Nov 18 '10 at 21:51
  • $\begingroup$ 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. $\endgroup$ – sleepless in beantown Nov 18 '10 at 22:22
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.