3 Replies - 1989 Views - Last Post: 04 November 2009 - 01:52 PM

#1 Nizbel99   User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Basic Graph Theory Proof - Help Needed

Post icon  Posted 03 November 2009 - 10:22 PM

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

Is This A Good Question/Topic? 0
  • +

Replies To: Basic Graph Theory Proof - Help Needed

#2 IngeniousHax   User is offline

  • |>|20-514<|{3|2

Reputation: 84
  • View blog
  • Posts: 1,385
  • Joined: 28-March 09

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.
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Danil*


Reputation:

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.
Was This Post Helpful? 0

#4 mojo666   User is offline

  • D.I.C Addict
  • member icon

Reputation: 409
  • View blog
  • Posts: 885
  • Joined: 27-June 09

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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1