Hello,

I have a combinatorics/graph theory assignment to do, and I'm stumped on one of the assignment questions, and I was wondering if I could have a little help/hints to get me on the right path.

The question states: Let G be a graph with P vertices, where P >= 1. If every vertex in G has a degree of atleast floor(p/2), prove that G is connected. (G is a simple graph).

I know that in order to show that G is connected, that we need to show that for any vertex v in G, that there exists a path from v to all other vertices in G. Normally, we are given a graph with a rule specifying what the set of vertices and what the set of edges are. So normally I can calculate what the neighbours of a vertex would be, and then from there prove that the graph is either connected or not.

But in this case, we have a generic graph, without much else given. So I'm not to sure as to how I would try to prove this. Since this is a introductory course to graph theory, I am only familar with some basic theorems and properties. Any help would be appreciated

Zach

# Basic Graph Theory Proof - Help Needed

Page 1 of 1## 3 Replies - 1989 Views - Last Post: 04 November 2009 - 01:52 PM

##
**Replies To:** Basic Graph Theory Proof - Help Needed

### #2

## Re: Basic Graph Theory Proof - Help Needed

Posted 03 November 2009 - 11:01 PM

Try using Mathbin.net ... I know it's good for lots of calculus stuff, yours is fairly above calc, but I'm sure there is someone on the site that could assist you.

### #3 Guest_Danil*

## Re: Basic Graph Theory Proof - Help Needed

Posted 04 November 2009 - 11:38 AM

This is easily proven with induction. Let the base case be P(2), that is, a graph of two points. Both points must have a degree of at least 1, which can only be achieved by connecting them together, creating a connected graph. Assuming that the theorem holds for some P(n) where n >= 2 we need to prove that it also holds for P(n+1). Any graph with P(n+1), that satisfies theorem's requirements, will have a portion of P connected points. The other point would have a degree of at least 1, because n >= 2, making it connected to that portion, making the whole graph connected. QED.

### #4

## Re: Basic Graph Theory Proof - Help Needed

Posted 04 November 2009 - 01:52 PM

You can also try a proof by contradiction. Assume there exists a disconnected graph with all vertices of degree floor(P/2). Try and construct this graph. Divide the vertices into two groups (A and B ) such that A is disconnected from B and the number of vertices in A >= the number of vertices in B. Now show that it is impossible for all vertices (More specifically the vertices of B ) to be degree of floor(P/2). This contradicts your assumption thus this graph cannot exist.

This post has been edited by **mojo666**: 04 November 2009 - 01:53 PM

Page 1 of 1