Show that a graph that is connected but not complete has vertices u,v and w such that uv and vw are edges but not uw.

Question

Show that if $G$ is connected and not complete, then $G$ has three vertices $u$, $v$ and $w$ such that $\{ (u, v), (v, w)\} \subseteq A(G)$ and $(u, w) \notin A(G)$.

I have the following: 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 think now we must find the shortest path from u to w. If G were a complete graph, we are done. Since G is not a complete graph, there must be some other path from v to w that is 2 or more long.

Answer 1

Your idea is fine: In a connected graph, we can define the distance $d(u,w)$ between two vertices $u,w$ as the length of the shortest path between them. In a complete graph, all distances are $\le1$, whereas here we have a non-complete graph, which means that some distances $>1$ exist. Among all vertex pairs of distance $>1$ let $(u,w)$ be of minimal distance $d=d(u,w)$. Let $v_0v_1\cdots v_d$ (with $v_0=u$ and $v_d=w$) be a path witnessing this distance. As $d(u,v_{d-1})\le d-1$, we conclude from the minimality that $d-1\le 1$. In other words, $d=2$. Thus with $v:=v_1$, the claim follows.

Answer 2

ETA: I saw your idea after I came up with my proof, your idea works as well.

---

Another proof: Let $W$ be a maximal clique in $G$ [note that $W$ may be just a single edge]. Then as $G$ is not complete, $W$ does not contain all vertices in $G$. As $G$ is connected this implies that there is an edge $u_2u_1 \in G$; $u_2 \in W$; $u_1 \not \in W$. So as $u_1$ is not in $W$ there is a vertex $u_3 \in W$ s.t. $u_1$ and $u_3$ do not form an edge in $G$. However, as both $u_2$ and $u_3$ are in the clique $W$ it follows that $u_2u_3$ is in $G$. So $u_1,u_2,u_3$ satisfy $u_1u_2 \in G$; $u_2u_3 \in G$; but $u_1u_3 \not \in G$.

Answer 3

Strategy: walk along your path finding the first vertex on that path that does not have an edge with each of the previous vertices.

For $k \in \Bbb{N}$, $k \geq 2$, let $P(k)$ be the predicate "the subgraph on the vertex set $\{v_0, \dots, v_k\}$ is a complete subgraph of $G$". Since $\{v_0, v_1\}$ is the vertex set of a complete subgraph of $G$, $P(2)$ is true. $P(n)$ is false. By well-ordering, there is a least element, $m$, of the interval $[2,n]$ such that $P(m)$ is false.

This says $G_{m-1} = \{v_0, v_1, \dots, v_{m-1}\}$ is the vertex set of a complete subgraph of $G$ and that $v_m$ does not have an edge with every element of $G_{m-1}$. Let $j$ be such that $0 \leq j \leq m-1$ and $(v_j, v_m) \not\in A(G)$. We know $\{ (v_j, v_{m-1}), (v_{m-1}, v_m) \} \subseteq A(G)$.

Answer 4

Consider $G = (V, E)$ as defining a binary relation $R$ such that $u\mathop{R}v$ if and only if either $u = v$ or the edge $uv \in E$. The relation $R$ is reflexive by definition, and it is symmetric because edges in a graph are undirected.

Suppose that for all $u, v, w \in V$, if $uv \in E$ and $vw \in E$ then $uw \in E$. In this case the relation $R$ is also transitive, making it an equivalence relation, so it partitions $V$ into equivalence classes such that all members of the same class are adjacent in the graph (i.e. each equivalence class is a complete subgraph), and members of different classes are not adjacent (i.e. different equivalence classes belong to different connected components).

Since $G$ has only one connected component, the relation $R$ must have a single equivalence class equal to the whole of $V$, implying $G$ is complete. This is a contradiction, so it follows that the supposition is false, i.e. there exist $u, v, w \in V$ such that $uv \in E$, $vw \in E$ but $uw \notin E$.