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

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

• You can always make more of an effort (that is, any effort at all) even if you don't know what to do. For example: for (1), have you tried drawing small examples of such graphs, and what is their diameter? for (2), what techniques do you know to find a Hamiltonian cycle? – Misha Lavrov Jan 25 at 15:18
• I have indeed and it seems to me that in every case (that is for 4,5,6 vertices) the diameter is always 2. But I wouldn't know how to justify it. I assume induction can be used to generalise it to more vertices but its something I still struggle with – totoro01 Jan 25 at 15:20
• It is better if you add your attempts to the question to begin with. – Misha Lavrov Jan 25 at 16:43

## 1 Answer

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.