Results 1 to 6 of 6

Math Help - Discrete Mathematics: Trees

  1. #1
    Newbie
    Joined
    May 2008
    Posts
    1

    Discrete Mathematics: Trees

    For which values of m and n is the complete bipartite graph on m and n vertices a tree?

    I'm using Discrete Mathematics 5th edition by Richard Johnsonbaugh, chapter 7.1 #5

    Please help I've been working on this problem for hours and I can't figure it out after reading a lot... I just don't understand. Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by hugs4smiles View Post
    For which values of m and n is the complete bipartite graph on m and n vertices a tree?

    I'm using Discrete Mathematics 5th edition by Richard Johnsonbaugh, chapter 7.1 #5

    Please help I've been working on this problem for hours and I can't figure it out after reading a lot... I just don't understand. Thank you!
    I'm having a difficult time understanding what the question is asking, I assume n stands for vertices, but what is m? Is there an illustration to accompany this question?

    Also, easy way to tell if a graph is bipartite, take two different coloured highlighters, mark a given node one colour, and then for every node on the graph, mark the nodes it connects to as the opposite colour. If any node requires both colours then it is not bipartite.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    In the attached graphic is the complete bipartite graph K_{3,4} .

    Johnsonbaugh defines a tree, T, as follows: T is a simple graph such that there us a unique path between any two vertices.

    Does the graph K_{3,4} fit that definition?
    Attached Thumbnails Attached Thumbnails Discrete Mathematics: Trees-k34.gif  
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by hugs4smiles View Post
    For which values of m and n is the complete bipartite graph on m and n vertices a tree?

    I'm using Discrete Mathematics 5th edition by Richard Johnsonbaugh, chapter 7.1 #5

    Please help I've been working on this problem for hours and I can't figure it out after reading a lot... I just don't understand. Thank you!
    I think its quite clear that for m =1 or n = 1, the bipartite is a tree. If either of m or n is greater than 1, you can prove there exists more than one path between two nodes.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by Isomorphism View Post
    If either of m or n is greater than 1, you can prove there exists more than one path between two nodes.
    Not quite.
    For any n if m=1 then it works.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    I am sorry, I meant:

    I think its quite clear that for m =1 or n = 1, the bipartite is a tree. If both m and n are greater than 1, you can prove there exists more than one path between two nodes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting, Probability, Trees, etc in Discrete Math
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: December 1st 2010, 12:58 PM
  2. discrete mathematics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2010, 05:39 PM
  3. What is discrete Mathematics About ?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: June 4th 2009, 09:28 PM
  4. Mathematics: Discrete-Mathematics (Algorithems)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 2nd 2008, 06:27 AM
  5. urgent hw trees-discrete maths!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 13th 2007, 10:45 PM

Search Tags


/mathhelpforum @mathhelpforum