Diameter of a graph such that given independent vertices u, v, d(u) + d(v) ≥ n.

Question

given my continuous struggle with proofs on graph theory, I come with another problem I do not know how to approach.

Given a graph G = (V, E) such that for any two non-neighboring vertices u, v ∈ V , d(u) + d(v) ≥ n. (n being the number of vertices) 1. Assuming G is not a clique, what is the diameter of such a graph? 2. Prove that in G there always exists a Hamiltonian cycle.

Thank you to any kind soul willing to help

Answer 1

To see that the diameter of this graph is always $2$, just take any two vertices $u$ and $v$ and look at the length $1$ and length $2$ paths between them.

If there is an edge $uv$, they are at distance $1$ and everything is good.

If there is no edge $uv$, then the condition $\deg(u) + \deg(v) \ge n$ applies. There are $n-2$ different possible length $2$ paths from $u$ to $v$, using the edges $ux$ and $xv$ for some third vertex $x$. Now apply the pigeonhole principle:

• There are at least $n$ edges incident to $u$ or to $v$.
• There are $n-2$ vertices $x \ne u,v$ in the graph.
• So at least $2$ of the $n$ edges must be incident to the same vertex $x$.

This gives us a path $ux, xv$ of length $2$.

You see that this proof actually works if we have $\deg(u) + \deg(v) \ge n-1$. We need $\deg(u) + \deg(v) \ge n$ for non-adjacent $u$ and $v$ for the second part of your question, which is just the statement of Ore's theorem.