IB Mathematics Applications & Interpretation Question Type 3: Using Adjacency Tables to Reconstruct Graphs or Check Graph Properties Exercises

Find the degree sequence of the graph whose adjacency matrix on vertices $1$–$6$ is:

$$A=\left(\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 0& 0& 1& 0& 1& 0\end{array}\right)$$

[3 marks]

Determine if the graph represented by

$$A=\left(\begin{array}{cccc}0& 2& 2& 2\\ 2& 0& 2& 2\\ 2& 2& 0& 2\\ 2& 2& 2& 0\end{array}\right)$$

is regular, and if so state its degree.

Decide whether the graph with adjacency matrix $A$ below has a Hamiltonian path.

$$A=\left(\begin{array}{ccccc}0& 1& 0& 1& 0\\ 1& 0& 1& 1& 1\\ 0& 1& 0& 1& 1\\ 1& 1& 1& 0& 0\\ 0& 1& 1& 0& 0\end{array}\right)$$

Construct the adjacency matrix of the directed graph with vertex set $\{1,2,3,4\}$ and directed edges: $1\to 2$, $2\to 3$, $3\to 1$, $3\to 4$, and $4\to 2$.

Given the adjacency matrix of a simple undirected graph on vertices $1,2,3,4$ as follows:

$$A=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right)$$

List all edges of the graph.

Determine whether the graph represented by the adjacency matrix $\mathbf{A}$ below is bipartite. Justify your answer.

$$\mathbf{A}=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right)$$

Determine whether the graph with the following adjacency matrix $A$ on vertices $1$ through $5$ is a tree:

$$A=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right)$$

The adjacency list of a graph $G$ is:

• A: B, D
• B: A, C, D
• C: B, D
• D: A, B, C

Determine whether $G$ is connected.

Given the weighted adjacency matrix $W$ of a connected undirected graph with vertices $\{1,2,3,4,5\}$:

$$W=\left(\begin{array}{ccccc}0& 2& 0& 6& 0\\ 2& 0& 3& 8& 5\\ 0& 3& 0& 0& 7\\ 6& 8& 0& 0& 9\\ 0& 5& 7& 9& 0\end{array}\right)$$

Find a minimum spanning tree using Kruskal’s algorithm. Show your working by listing the edges in the order they are selected and state the total weight of the tree.

For the graph with adjacency matrix

$$A=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}\right)$$

determine the number of connected components.

Using the adjacency matrix below, find a shortest path from vertex $1$ to vertex $5$ in the unweighted graph.

$$A=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right)$$

Check whether the graph given by the adjacency matrix below has an Eulerian circuit:

$$A=\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 1& 1\\ 1& 1& 0& 1& 0\\ 0& 1& 1& 0& 1\\ 0& 1& 0& 1& 0\end{array}\right)$$