# Bipartite Graphs

Computer Science Level 3

Which of the following adjacency matrices represent a bipartite graph?

$\text{A} = \left(\begin{array}{ccccc}0 & \color{red}{1} & \color{red}{1} & 0 & 0 \\ \color{red}{1} & 0 & 0 & \color{red}{1} & 0 \\\color{red}{1} & 0 & 0 & 0 & 0 \\0 & \color{red}{1} & 0 & 0 & \color{red}{1} \\0 & 0 & 0 & \color{red}{1} & 0\end{array}\right), \quad \text{B} = \left(\begin{array}{ccccc}0 & \color{blue}{1} & 0 & \color{blue}{1}& 0 \\ \color{blue}{1} & 0 & \color{blue}{1} & 0 & \color{blue}{1} \\0 & \color{blue}{1} & 0 & \color{blue}{1} & 0 \\ \color{blue}{1} & 0 & \color{blue}{1} & 0 & \color{blue}{1} \\0 & \color{blue}{1} & 0 & \color{blue}{1} & 0\end{array}\right)$

$\text{C} = \left(\begin{array}{ccccc}0 & 0 & \color{green}{1} & 0 & 0 \\0 & 0 & \color{green}{1} & 0 & 0 \\\color{green}{1} & \color{green}{1} & 0 & \color{green}{1} & \color{green}{1} \\0 & 0 & \color{green}{1} & 0 & 0 \\0 & 0 & \color{green}{1} & 0 & 0\end{array}\right)$

×