Graph Theory Problem about connectedness

75 Views Asked by At

Problem:

Let $G$ be a graph and $d(u)+d(v)+d(w)\geq(n-1)$ where $u$, $v$ and $w$ are three non adjacent vertex to each other, then prove that $G$ is a connected graph.

Approach:

$u$, $v$ and $w$ are not adjacent to each other so $d(u)\leq(n-3),$ $d(v)\leq(n-3)$, $d(w)\leq(n-3)$ Therefore we can say that $(n-1)\leq d(u)+d(v)+d(w)\leq 3(n-3)$. Then what?? I don't know..

1

There are 1 best solutions below

0
On

I can't find a version of the statement that claims that $G$ is connected that is true (see the counterexamples in the comments on the question). However, one can prove that if $G$ satisfies the property that for all triples of pairwise nonadjacent vertices $u,v,w$, $d(u)+d(v)+d(w)\ge n-2$, then $G$ has at most 2 connected components.

Proof:

If $G$ is connected then we are done, so suppose $x$ and $y$ are two vertices of $G$ with no path between them. Certainly $x$ and $y$ must be nonadjacent. Further if $N(x)\cap N(y)\ne \varnothing$, then there is some vertex $z$ adjacent to both $x$ and $y$, which would imply that $xzy$ is a path from $x$ to $y$. Hence we also know that $N(x)\cap N(y)=\varnothing$.

Now for every other vertex $z$ of $G$ either $z$ is adjacent to $x$, adjacent to $y$, or adjacent to neither. If $z$ is adjacent to neither $x$ nor $y$, then we know that $d(x)+d(y)+d(z) \ge n-2$. Since $x,y,z$ are pairwise nonadjacent, $N(x)\cup N(y)\cup N(z) \subseteq V\setminus \{x,y,z\}$. Thus by pigeonhole, there is at least one vertex that is in at least two of the sets $N(x)$, $N(y)$, or $N(z)$. Since $N(x)$ and $N(y)$ are disjoint, this implies that $z$ shares a neighbor with at least one of $x$ or $y$. Thus all vertices of $G$ lie in the connected component of either $x$ or $y$.