Results 1 to 4 of 4

Math Help - graph + tree

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    graph + tree

    If a graph has
    8 verticies:
    2 with 1 degree
    1 with 2 degrees
    5 with 3 degrees.

    If it is not a tree I must prove why.

    The only way I can think of to do this is to draw the graph (which I can't replicate here).
    When I draw the graph I find I have 2 non-trivial circuits, therefore the graph is not a tree.
    Is this the only way to prove the graph is not a tree?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    29
    For your graph to be a tree then \epsilon = v-1 where \epsilon = number of edges and v = number of vertices which is given to be 8.

    To check you need to find the number of edges. \epsilon = \frac{1}{2}\sum d(v) where d(v) is the degree of each vertex. Does this equal 8-1 = 7 ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    ok,
    I understand that the edges = vertices -1 for a tree.
    So for 8 vertices there should be 7 edges.

    (I can draw this, bu t I get non-trivial circuits. Therefore not a tree)

    But to prove it, I use

    edge = vertices - 1.
    edge = \frac{1}{2} * v1 degrees + v2 degrees... vn degrees

    edge = 7
    edge = 0.5 * (1+1+2+3+3+3+3+3)
    = 0.5 * 19
    = 9.5

    7 != 9.5, therefore not a tree.

    correct?

    btw, thanks for taking the time to help pickslides.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Master Of Puppets
    pickslides's Avatar
    Joined
    Sep 2008
    From
    Melbourne
    Posts
    5,236
    Thanks
    29
    looks good to me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory:Tree
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 22nd 2011, 05:23 PM
  2. Every connected graph contains a maximal tree
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 4th 2011, 07:44 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 6
    Last Post: November 12th 2010, 08:03 AM
  5. simple graph is a tree?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum