A simple graph has 20 vertices. Any two distinct vertices u and v are such that deg(u) + deg(v) greater than or equal to 19. Prove that the graph is connected. Note that a connected graph is a graph such that there exists a path between all pairs of vertices.

Any help provided will be greatly appericiated.

2. Suppose by contradiction that the graph is disconnected. At least one connected component, let's call it $\displaystyle A$, would have less than 10 vertices.
The vertices of $\displaystyle A$ are only connected to vertices in $\displaystyle A$, so they have at most 9 neighbours.
1) if the cardinality of $\displaystyle A$ is at least 2, take $\displaystyle u$ and [tex]v[/Math] inside $\displaystyle A$. This leads to a contradiction.
2) if the cardinality of $\displaystyle A$ is 1, the cardinality of the complement of $\displaystyle A$ is 19 and the degree of vertices in the complement is hence less than 18. Take $\displaystyle u\in A$ (in fact [tex]A=\{u\}[/Math] so it is not connected to any other vertex) and $\displaystyle v$ outside $\displaystyle A$. Then $\displaystyle {\rm deg}(u)+{\rm deg}(v)={\rm deg}(v)$, and you get another contradiction.

3. There is a typo in my question it should have been deg(u) + deg(v) greater than or equal to 19. The solution still stands right ?

4. Originally Posted by tester85
There is a typo in my question it should have been deg(u) + deg(v) greater than or equal to 19. The solution still stands right ?
I can't remember what you wrote first, but this is what I understood anyway, so my proof works.

5. Ok. Great thanks.