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

  • $\begingroup$ 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? $\endgroup$ – Misha Lavrov Jan 25 at 15:18
  • $\begingroup$ 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 $\endgroup$ – totoro01 Jan 25 at 15:20
  • $\begingroup$ It is better if you add your attempts to the question to begin with. $\endgroup$ – Misha Lavrov Jan 25 at 16:43

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.


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.