Discrete Mathematics: Trees

• May 14th 2008, 10:19 PM
hugs4smiles
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!
• May 15th 2008, 02:13 AM
angel.white
Quote:

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.
• May 15th 2008, 08:06 AM
Plato
In the attached graphic is the complete bipartite graph \$\displaystyle 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 \$\displaystyle K_{3,4} \$ fit that definition?
• May 15th 2008, 08:17 AM
Isomorphism
Quote:

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.
• May 15th 2008, 08:41 AM
Plato
Quote:

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.
• May 15th 2008, 09:19 AM
Isomorphism
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.