Graph theory: Question about graph that is connected but not complete.

Question

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.

Answer 1

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$.

Answer 2

You may simply suppose the contrary. If $uv,vw\in E \Rightarrow uw\in E$ holds for all $u,v,w$ then $E$ gives an equivalence relation in which equivalence classes are connected components in which every pair of elements is connected. As $G$ is connected, it must be complete.