Results 1 to 6 of 6

Math Help - Graph Theory - Connection

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    42

    Graph Theory - Connection

    Let G be a graph with n ≥ 2 vertices. Prove that if δ(G) ≥ (1/2)n, then G is connected.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Could you remind what δ(G) is?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    42
    δ(G) is the minimum degree of a vertex in G.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I think that under this condition not only G is connected, but every 2 vertices have a path between them of length at most 2.

    Let V be the set of vertices. Take any 2 distinct vertices a and b. If they are connected by an edge, fine. Suppose there is no direct edge. Let U=V-{a,b}; then |U| = n-2. Now, a is connected with at least n/2 vertices. If a does not have a loop, then all those n-2 vertices are in U. Similar thing holds for b. So, those two subsets of U must intersect.

    Please let me know if loops are permitted in this problem.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    42
    Loops are not permitted.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I hope that this solves the problem then.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum