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

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.

• Please don't assign tags if you don't know what they mean. This question has nothing whatsoever to do with rough-path theory. – saulspatz Apr 7 at 19:58

## 4 Answers

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.

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

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

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