• Oct 17th 2008, 01:49 AM
tester85
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.
• Oct 17th 2008, 01:06 PM
Laurent
Suppose by contradiction that the graph is disconnected. At least one connected component, let's call it $A$, would have less than 10 vertices.
The vertices of $A$ are only connected to vertices in $A$, so they have at most 9 neighbours.
1) if the cardinality of $A$ is at least 2, take $u$ and $$v$$ inside $A$. This leads to a contradiction.
2) if the cardinality of $A$ is 1, the cardinality of the complement of $A$ is 19 and the degree of vertices in the complement is hence less than 18. Take $u\in A$ (in fact $$A=\{u\}$$ so it is not connected to any other vertex) and $v$ outside $A$. Then ${\rm deg}(u)+{\rm deg}(v)={\rm deg}(v)$, and you get another contradiction.
• Oct 17th 2008, 06:52 PM
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 ?
• Oct 18th 2008, 06:50 AM
Laurent
Quote:

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.
• Oct 18th 2008, 07:11 AM
tester85
Ok. Great thanks.