Finding the conclusion on converse statement of a result in graph theory.

110 Views Asked by At

It is known that for a graph $G$ of order $n$ if $deg(u) + deg(v) \geq n-1$ then $G$ is connected and diameter is less than or equal to two, for every non adjacent vertices $u$ and $v$.

I was wondering if the reverse is true? If given that $G$ is a connected graph with eccentricity of every vertex as two (obviously diameter is two here), then can we conclude that $deg(u) + deg(v) \geq n-1$ for arbitrary non adjacent vertices $u$ and $v$ in $G$?

2

There are 2 best solutions below

1
On

Nope: take a Star with $n-1$ leaves. It has diameter two but every two leaves have degree sum two.

0
On

Take the complete bipartite graph $K_{2,n-2}$. Then the eccentricity of every vertex is $2$: each vertex is $2$ steps away from a vertex on the same side of the bipartition (and $1$ step away from a vertex on the opposite side).

However, the degree condition is not satisfied: if $x,y$ are on the side of the bipartition with $n-2$ vertices, then $\deg(x) + \deg(y) = 2 + 2 = 4$.

In general, any complete bipartite graph $K_{a,b}$ with $a > 1$ and $b>1$ will be a connected graph in which all vertices have eccentricity $2$, but $\deg(x)+\deg(y)$ will have values of either $2a$ or $2b$ for any non-adjacent vertices $x$ and $y$, depending on which side of the bipartition they're on.

(It must be admitted that this solution is a simple modification of Bob Krueger's solution: a star with $n-1$ leaves is $K_{1,n-1}$.)