# Math Help - Discrete Mathematics: Trees

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!

2. Originally Posted by hugs4smiles
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.

3. 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?

4. Originally Posted by hugs4smiles
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.

5. Originally Posted by Isomorphism
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.

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.