Results 1 to 4 of 4

Math Help - Show that if δ+Δ >= n-1, G is connected

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    19

    Show that if δ+Δ >= n-1, G is connected

    I think I'm almost there but I'm messing up on some step or two...

    Suppose G is not connected, therefore G has two or more components such that C1 + C2 + C3+ ... + CM = n

    Let Δ belong to C1, therefore C1 has size Δ+1.

    C1 + C2 <= n
    Δ+1 + C2 <= n
    C2 <= n-Δ-1

    Δ+1+n-Δ-1 <= n
    Δ+1+(n-Δ-2) <= n-1
    Δ+1+δ <= n-1
    Δ+δ <= n-2
    Δ+δ < n-1

    Therefore if δ+Δ >= n-1, G is connected

    Any tips, I think this proof looks a little weak and I'm pretty sure I'm messing up on the δ. For a disconnected graph I'm pretty sure that δ=n-Δ-#of components, but I'm not sure if I'm allowed to just put that in.

    Thanks guys
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2009
    Posts
    19
    dunno why i post here, never get any help anyway
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    Have to properly introduce new concepts and variables

    Hi,

    I can guess from your description that the subject is graphs, but it's hard to understand anything else. If you want that people who don't know anything about this particular problem understand it (and then help), you have to carefully describe every object that you use.

    So G is probably a graph, but what are C1, etc? Later you say "Let Delta belong to C1." Does this make C1 a set? How do you add sets then? Is this set union? What is Delta and n? Without this knowledge the description is incomprehensible.

    Evgeny
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1
    Quote Originally Posted by glover_m View Post
    dunno why i post here, never get any help anyway
    glover_m;402972 Please read the above posting. It beautifully answers why no one has bothered to answer your post.
    I wonder why in the world you think that any of us knows what those strings of obscure symbols is about?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Show that I^n and S^n are path-connected?
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 29th 2011, 07:51 PM
  2. Show that I^n and S^n are path-connected?
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: November 29th 2011, 05:00 PM
  3. show the space is connected
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 11th 2011, 11:41 PM
  4. show why domain D is not simply connected.
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 14th 2011, 02:41 AM
  5. Show sets not connected
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 27th 2009, 09:05 PM

Search Tags


/mathhelpforum @mathhelpforum