Clarification of Bondy's proof that an Ore graph on $n$ vertices has $\geq \frac{n^2}{4}$ edges This question concerns a proof from Bondy, Pancyclic Graphs 1 of the fact that a graph $G$ on $n$ vertices satisfying the condition that $d(u) + d(v) \geq n$ for any non-adjacent vertices $u,v$ has at  least $\frac{n^2}{4}$ edges. The proof is:

Let $k$ be the minimum vertex degree in $G$. We assume that $k < \frac{n}{2}$ (otherwise there is nothing to prove). If there are $m$ vertices of degree $k$, then by Ore's condition, all of these vertices must be joined to one another. Hence $m 
\leq k + 1$, and $m \neq k+1$ since G is Hamiltonian (and therefore connected). There are at least $n-k-1$ vertices of degree at least $n-k$ in G, namely those vertices that are not joined to one specific vertex of degree $k$.

After this, the lower bound follows. I don't follow the last part, namely that there are at least $n-k-1$ vertices of degree $n-k$ in $G$. I understand that if a vertex $v$ is not adjacent to all vertices of degree $k$ (i.e. there is a vertex of degree $k$ not adjacent to $v$) then $d(v) \geq n-k$ by the Ore condition.
But where does the $n-k-1$ estimate come from? I suppose it's a lower bound for $n-m - 1$ (since $m \leq k$) but if that's the case I don't see why there should be at most one vertex of degree $>k$ connected to all vertices of degree $k$.
 A: If $\deg(v) = k < \frac n2$, then out of the $n$ vertices in the graph, you have:

*

*One vertex which is $v$;

*$k$ vertices which are neighbors of $v$;

*$n-k-1$ vertices which are not neighbors of $v$.

If a vertex $w$ is in the third category, then Ore's condition says $\deg(v) + \deg(w) \ge n$, hence $\deg(w) \ge n-k$. So all vertices in the third category have degree at least $n-k$.

That answers your question, but let me also try to say a bit about what the proof is doing and why.
The proof leads with the $m \ne k+1$ reasoning because that's where it logically should go, but it's educational to see what happens if we try to continue without doing it.
Then we can see from the above that we have $k+1$ vertices of degree at least $k$, and $n-k-1$ vertices of degree at least $n-k$. The number of edges is half the sum of the degrees, so it is at least $$\frac12k(k+1) + \frac12(n-k)(n-k-1).$$ We can rewrite this as $(k - \frac{n-1}{2})^2 + \frac{n^2-1}{4}$, which is at least $\frac{n^2-1}{4}$ because $(k - \frac{n-1}{2})^2 \ge 0$.
We want to get at least $\frac{n^2}{4}$ edges and we are nearly there! The only way that we can end up below this number is if $k = \frac{n-1}{2}$ (so that $(k - \frac{n-1}{2})^2=0$) and if all of our inequalities up until this point are tight: all vertices in the second category have degree exactly $k$, and all vertices in the third category have degree exactly $n-k$. If this were possible, we'd only have $\frac{n^2-1}{4}$ edges.
This is where the reasoning the proof leads with comes in. If all vertices in the second category have degree $k$, then you have $k+1$ vertices of degree $k = \frac{n-1}{2}$; then all of them must be adjacent, because otherwise we'd violate Ore's condition. That already gives $k$ neighbors to each of those $k+1$ vertices, so they must not have any additional neighbors: they form a $(k+1)$-vertex clique. This is a problem for two reasons:

*

*As the proof says, this makes the graph disconnected, which violates Ore's theorem that it must actually be Hamiltonian.

*Alternatively, we reason that the other $n-k-1 = \frac{n-1}{2}$ vertices can have degree at most $\frac{n-3}{2}$, because they can only be adjacent to each other; but they were supposed to have degree $n-k = \frac{n+1}{2}$, instead.

So this exceptional situation with only $\frac{n^2-1}{4}$ edges is impossible, and therefore we always have at least $\frac{n^2}{4}$.
