We have a simple graph $G=(V,E)$ such that
$$\mathrm{deg}(u)+\mathrm{deg}(v)\ge |V|-1$$
I've read several threads about such a graph which prove that it has to be connected with diameter at most $2$. My question is
Is it possible to have two distinct non-adjacent pairs of vertices in $G$ such that their degree sum is exactly $n-1$??
(Note that two pairs are distinct even if one of the elements is common in them.)I need this result in the proof of a theorem, if this is true, I'll be done. If true, please help me with a proof of this, otherwise please present a counter example.
Best Answer
One example is the $5$-cycle, in which any two of the five vertices have degree sum exactly $4$.
(More generally, for any even $k$, any $k$-regular graph with $2k+1$ vertices will have lots of such pairs. We want $k$ to be even because a $k$-regular graph with $2k+1$ vertices doesn't exist for odd $k$.)