×
Discrete Mathematics

# Bipartite Graphs

Every circle is a chemical compound, and every line means that the two compounds cannot be put together or they will explode. Can all the compounds be safely stored in two different beakers without exploding?

Is a graph with 10 nodes and no edges bipartite?

Note: A graph is considered bipartite if its nodes can be split into two separate groups where no two nodes in the same group are connected by an edge.

An evil host has 7 guests over for dinner, and has two rooms. He wants to put the guests into the two rooms such that no two people in any room know each other. What is the maximum possible number of relationships among the 7 guests if it is possible for the host to arrange them in this fashion.

Note: A relationship is two people who know each other, and it is assumed that if some person knows another, then that other person knows the first one.

True or false: the nodes of a tree can be colored red and blue with no two nodes of the same color being connected by an edge.

Note: A graph is a tree if it has no cycles (between every two nodes, there is one, and exactly one, path).

Can you color every node of this graph white or black such that no two nodes of the same color are connected by an edge?

×