Results 1 to 3 of 3

Math Help - graph

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    tehran
    Posts
    15

    graph

    suppose G is a connected graph with n vertices and n-1 edges.
    prove that G has at least 2 vertices with deg(v)=1 .
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,539
    Thanks
    778

    Re: graph

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1

    Re: graph

    Quote Originally Posted by mshou View Post
    suppose G is a connected graph with n vertices and n-1 edges.
    prove that G has at least 2 vertices with deg(v)=1 .
    Recall that |\mathcal{V}| is the number of vertices and |\mathcal{E}| is the number of edges.

    Then we know that \frac{2|\mathcal{E}|}{|\mathcal{V}|}\ge m where m is the minimum vertex degree.

    You can use that show that if |\mathcal{V}|=n-1 then there must be at one vertex of degree one.

    You are working with a connected graph. So all vertices are of degree alt least one.

    You should know that \sum\limits_{v \in\mathcal{V}} {\deg (v)}  = 2\left| \mathcal{E} \right|.

    Now you show some effort.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. Replies: 7
    Last Post: August 5th 2011, 01:30 PM
  3. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM
  5. Replies: 1
    Last Post: February 15th 2009, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum