# Thread: Graph theory proof-diameter/degree relationship

1. ## Graph theory proof-diameter/degree relationship

Hi, all!
Here's the problem I've been working on.

Suppose G is connected and suppose every $\displaystyle x \in V(G)$ satisfies $\displaystyle \delta (x) \geq \fraq{(v-1)/2}$.Show that G has diameter no greater than 2.

Where $\displaystyle \delta (x)$ is the degree of a vertex.
So, it shouldn't be hard, but I can't seem to get what the relationship between the degree of a vertex of a graph and its diameter is.
Any help would be greatly appreciated!
Thanks!

2. Pick a pair of vertices $\displaystyle u$ and $\displaystyle w$, we have to prove that the distance between them is at most 2.

If $\displaystyle u$ and $\displaystyle w$ were adjacent, we are done, their distance is not greater than 2.

We consider now the case in which $\displaystyle u$ and $\displaystyle w$ are not adjacent.

Suppose the statement were false, that is, each of the neighbours of $\displaystyle u$ is not a neighbour of $\displaystyle w$.

Since $\displaystyle \delta (w) \geq {\frac{v-1}{2}}$ we have $\displaystyle \delta(u) \leq v - 2 - \delta(w) \leq v - 2 - \frac{v-1}{2} < {\frac{v-1}{2}}$ a contradiction since $\displaystyle \delta(u)\geq {\frac{v-1}{2}}$ !

The -2 comes from the fact that $\displaystyle u$ can't be a neighbour of itself or $\displaystyle w$.

Note that we didn't use the hypothesis that G was connected, but we needed $\displaystyle G$ to be a simple graph .