# Please help ! Graph problem

Printable View

• Oct 17th 2008, 01:49 AM
tester85
Please help ! Graph problem
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 $\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.
• 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.