Computer Science

# Graphs: Level 3 Challenges

If $G$ is a graph with 61 vertices and 60 edges, then:

Find the $10 \times 10$ adjacency matrix $A$ of the graph above.

Input $\det \left( \frac{( A^2 + A - K )}{2} \right)$ as your answer.

Details and assumptions

• $K$ is the $10 \times 10$ matrix which has $1$ for all entries.

Which of the following adjacency matrices represent a bipartite graph?

$\text{A} = \left(\begin{array}{ccccc}0 & \color{#D61F06}{1} & \color{#D61F06}{1} & 0 & 0 \\ \color{#D61F06}{1} & 0 & 0 & \color{#D61F06}{1} & 0 \\\color{#D61F06}{1} & 0 & 0 & 0 & 0 \\0 & \color{#D61F06}{1} & 0 & 0 & \color{#D61F06}{1} \\0 & 0 & 0 & \color{#D61F06}{1} & 0\end{array}\right), \quad \text{B} = \left(\begin{array}{ccccc}0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1}& 0 \\ \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} \\0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0 \\ \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} \\0 & \color{#3D99F6}{1} & 0 & \color{#3D99F6}{1} & 0\end{array}\right)$

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

×