2
$\begingroup$

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.

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

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.