# 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 $x \in V(G)$ satisfies $\delta (x) \geq \fraq{(v-1)/2}$.Show that G has diameter no greater than 2.

Where $\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 $u$ and $w$, we have to prove that the distance between them is at most 2.

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

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

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

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

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

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