Solution to If a simple graph G has p vertices and any two distinct vertices u and … - Sikademy
Author Image

Archangel Macsika

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

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-2756-qpid-1288