Results 1 to 5 of 5

Thread: 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; Oct 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 $\displaystyle A$, would have less than 10 vertices.
    The vertices of $\displaystyle A$ are only connected to vertices in $\displaystyle A$, so they have at most 9 neighbours.
    1) if the cardinality of $\displaystyle A$ is at least 2, take $\displaystyle u$ and [tex]v[/Math] inside $\displaystyle A$. This leads to a contradiction.
    2) if the cardinality of $\displaystyle A$ is 1, the cardinality of the complement of $\displaystyle A$ is 19 and the degree of vertices in the complement is hence less than 18. Take $\displaystyle u\in A$ (in fact [tex]A=\{u\}[/Math] so it is not connected to any other vertex) and $\displaystyle v$ outside $\displaystyle A$. Then $\displaystyle {\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: Dec 29th 2011, 04:43 AM
  2. graph problem..
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Sep 12th 2009, 08:13 AM
  3. a graph problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 10th 2009, 04:32 PM
  4. Graph Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Jul 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