Answer to Question #221007 in Discrete Mathematics for Ankita

Question

If a simple graph G has p vertices and any two distinct vertices u and v of G have the

property that degGu + degGv ≥ p-1 then prove that G is connected

Answer 1

Assume that $G$ is disconnected, that is there exist two vertices, $u$ and $v$, such that there is no path in $G$ between them. Let $U$ be the set of vertices incident to the vertex $u$, and $V$ be the set of vertices incident to the vertex $v$. Since $u$ and $v$ are not incident, then $u\notin V$ and $v\notin U$.

If $U\cap V=\empty$ then all the sets $\{u\},\,\{v\},\,U,\,V$ are disjoint.

Hence, $|\{u\}|+|\{v\}|+|U|+|V|\leq |G|$, or equivalently, $1+1+\deg_Gu+\deg_Gv\leq p$, and $\deg_Gu+\deg_Gv\leq p-2$, that is a contradiction to the condition $\deg_Gu+\deg_Gv\geq p-1$.

From this it follows that the assumption $U\cap V=\empty$ is false, i.e. there exists a vertex $w\in U\cap V$. Thus, $w$ is incident to both the vertices $u$ and $v$, and $u-w-v$ is a path in $G$, connecting $u$ and $v$, that is a contradiction with assumption that $G$ is disconnected.

Therefore, $G$ is a connected graph.