If $G$ is disconnected and the vertices $x,y$ are adjacent in $G$, then there is a vertex that isn't adjacent to $x$ and isn't adjacent to $y$.

Question

I'm just starting graph theory and I'm trying to prove the following:

Let $G$ be a simple disconnected graph with vertex set $V(G)$ and edge set $E(G)$. If $x,y\in V(G)$ and $xy \in E(G)$, then $\exists z \in V(G)$ such that $xz,yz \notin E(G)$.

Here's my attempt:

We proceed by contradiction. Suppose instead that $\forall z \in V(G)$, $xz\in E(G)$ or $yz \in E(G)$. Since $G$ is disconnected, we know by definition that $\exists a,b \in V(G)$ such that $a$ and $b$ do not belong to the same path. By letting $z=a$, we know that $ax\in E(G)$ or $ay \in E(G)$. In either case, there must be a path from $a$ to $x$ (the path will either be $ax$ or $ayx$). Similarly, by letting $z=b$, there must be a path from $b$ to $x$ (the path will either be $bx$ or $byx$). Hence, there is a path from $a$ to $b$ that passes through at least one of $\{x,y\}$ (the path will be either $axb$, $axyb$, $ayxb$, or $ayb$), a contradiction. So $\exists z \in V(G)$ such that $xz,yz \notin E(G)$, as desired.

Is my proof correct? I'm fairly sure it is, but it feels overly long. Can parts of my proof be omitted? Is there a shorter, more elegant proof that doesn't rely on case analysis? Maybe a direct proof (not a proof by contradiction) would be faster? Side Note: I haven't covered the definition of a connected component yet.

Answer 1

I’m assuming from the wording of the question that for you a graph is disconnected if there are vertices $a,b\in V(G)$ such that no path contains both $a$ and $b$. If that’s the case, your proof is indeed correct, and you can’t really shorten it much. You could do something like this to organize it a little more clearly:

Suppose that every vertex of $G$ is adjacent to at least one of $x$ and $y$. Let $$X=\{v\in V(G):vx\in E(G)\}$$ and $$Y=\{v\in V(G):vy\in E(G)\}\;;$$ by hypothesis $X\cup Y=V(G)$. If $u,v\in X$, then $uxv$ is a path from $u$ to $v$, and if $u,v\in Y$, then $uyv$ is a path from $u$ to $v$. Finally, if $u\in X$ and $v\in Y$, then $uxyv$ is a path from $u$ to $v$. It follows that $G$ is connected.

Answer 2

Since the graph is disconnected, we can split $V$ into the disjoint union of 2 non-empty set of vertices, where there are no edges between a vertex from the first set and a vertex from the second set. $x, y$ must both below to 1 set. Let $z$ be any vertex in the other set. We're done.

---

I do not know what you mean by "a" and "b" do not belong to any path. I'm guessing you mean that both "a" and "b" do not belong to the same path, though it's possible for "a" to belong to one path and "b" to belong to another path.

Answer 3

This is an attempt to tidy up the thinking you have already done, and it deals with one of the endpoints of the path being $x$ or $y$ - it is important not to miss such cases.

Let $G_x, G_y$ be the sets of vertices adjacent to $x, y$ respectively. Note that $x\in G_y, y\in G_x$. We are given that $G$ is disconnected.

For a contradiction assume that all vertices are in one of the two sets (some may be in both) so that $G=G_x\cup G_y$. Let $a, b$ be an arbitrary pair of vertices. If they in the same set, say $G_x$, we have a path $axb$. If they are in different sets, say $a\in G_x, b\in G_y$ we have a path $axyb$.

Therefore if $G=G_x\cup G_y$ we can connect any pair of vertices in $G$, and $G$ is connected. [contradiction]