In 1989, Faudree proved this theorem:
Theorem Let $G$ be a 2-connected graph with $n\ge 3$ vertices. If $|N(x)\cup N(y)|\ge \frac{2(n-1)}{3}$ for any $xy\notin E(G)$, then $G$ is Hamiltonian.
- Faudree R J, Gould R J, Jacobson M S, et al. Neighborhood unions and Hamiltonian properties in graphs[J]. Journal of Combinatorial Theory, Series B, 1989, 47(1): 1-9.
I would like to reduce the graphs to planar graphs.
- Is there a class of planar graphs that satisfy that $|N(x)\cup N(y)|\ge \frac{2(n-1)}{3}$ for any $xy\notin E(G)$? It is not yet clear how to construct them.
I can find some small graphs, for example $C_4$. I'm wondering if there really is a planar graph that satisfies the condition when $n$ is very large. In particular, how about the maximal planar graphs?
Edits: I just find that $C_4$ does not meet the conditions either.
Edit: Thanks for radekzak's code. By his answer, there are two vertices in a planar graph with $n$ vertices such that $|N(x)\cup N(y)|\le 5+5=10.$
So the graph that satisfies the condition requires the following equation $$10\ge \frac{2(n-1)}{3}$$
to hold.
Thus, we have $n\le 16$.
So the remaining task is to find these planar graphs with at most $16$ vertices. I have doubts whether such planar graphs even exist.
Edits: For exmaple, $C_5.$ Note that $|N(x)\cup N(y)|=3> 2(5-1)/3$ for any $xy\notin E(G)$.
Intuitively, graphs for which the theorem hold are quite dense, and planar graphs are sparse. Therefore, there should not be any examples if $n$ is large enough.
Indeed, in any planar graph there is a vertex of degree at most $5$, let's say it is $v$. Let us erase $v$ together with its neighbours. We get another planar graph, and it has some vertex $w$ of degree at most $5$. Then $|N(v) \cup N(w)| \leqslant 10$, so when $n > 16$ there are no examples.