Bipartite Graphs and Trees Questions

1.1k Views Asked by At

Which of the claims below is not equivalent to the rest?

1) Every cycle in a graph "B" has an even length

2) Graph "B" is bipartite

3) Graph "B" has two components that are connected.

4) Graph "B" is two-colorable.

Which of the claims below is not equivalent to the rest?

1) Graph "B" is connected and contains no cycles

2) Graph "B" is a tree

3) The maximum degree of "B" is 2.

4) In Graph "B" there is a unique simple path between any 2-vertices.

1

There are 1 best solutions below

9
On BEST ANSWER

For part (a) Konig's Theorem states that a graph is bipartite if and only if all any cycles present are of even length.

Note that bipartite graphs need not be connected. Consider a graph $G(V, E)$ with $E = \emptyset$. Bipartite and two-colorability are equivalent. I've edited to fix my mistake.

For part (b), consider a star. Is that a tree? The rest of those follow from the definition of a tree.