Thread: 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.

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

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 ?

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.

Ok. Great thanks.