Question: Prove that if a graph $G=(V,E)$ is connected, but not complete, then there are vertices $u,v$ and $w$ such that $uv,vw \in E$ but $uw \notin E.$
My attempt so far:
Since G is not complete, we know that there exists vertices u and w that do not have an edge connecting. G is connected, meaning that there is a path for any two vertices, and the shortest path between them would be $V = v_0, v_1, … v_n = W$ from v to w.
I have an intuition that tells me the proof involves finding the shortest path from u to w. If G was a complete graph, the shortest path from u to w would simply be 1; however, since G is NOT a complete graph, there must be some other path from v to w that has length of 2 or more.
I think proving that the shortest path from u to w would have length 2+ would be the whole proof, but I don't know where to start.
Can someone correct me if I am wrong or help me with the next step? Thank you.
Best Answer
HINT: You’re looking in the right direction, but you need to pick $u$ and $w$ more carefully: among all pairs of vertices with no edge between them, let $\{u,w\}$ be a pair with the shortest path from $u$ to $w$. (There may be more than one such pair, in which case you can pick any of them.) Now show that if the path is not of length $2$, you can replace $u$ by a vertex $u'\ne w$ to get a pair $\{u',w\}$ of vertices with no edge between them and a shorter path between them, contradicting the choice of $u$ and $w$.