Results 1 to 5 of 5

Math Help - Please help ! Graph problem

  1. #1
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160

    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.
    Last edited by tester85; October 17th 2008 at 06:48 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

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

  3. #3
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by tester85 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Ok. Great thanks.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ti-83 sin graph problem
    Posted in the Calculators Forum
    Replies: 5
    Last Post: December 29th 2011, 04:43 AM
  2. graph problem..
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: September 12th 2009, 08:13 AM
  3. a graph problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 10th 2009, 04:32 PM
  4. Graph Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 4th 2007, 11:47 AM
  5. A Graph Problem :?
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: May 15th 2007, 11:23 AM

Search Tags


/mathhelpforum @mathhelpforum