IB Mathematics Applications & Interpretation Question Type 1: Determining Properties of a Given Simple Graph Exercises

A simple graph $G$ has adjacency matrix $$\left(\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 1& 1& 0\\ 1& 1& 0& 1& 1\\ 0& 1& 1& 0& 1\\ 0& 0& 1& 1& 0\end{array}\right)$$ Determine the number of connected components and identify them.

In a simple undirected graph $G$ with 6 vertices and 9 edges, calculate the sum of degrees of all vertices and confirm the Handshaking Lemma.

Decide whether the simple graph with vertices $\{V_1,V_2,V_3,V_4,V_5\}$ and edges $\{V_1,V_2\},\{V_2,V_3\},\{V_3,V_4\},\{V_4,V_5\},\{V_5,V_1\}$ is complete, connected, and contains any circuits. Justify your answers.

Given the degree sequence $(4,3,3,3,2,1)$, determine if it is graphical, and if so, use the Havel–Hakimi algorithm to construct a corresponding simple graph.

Given the simple graph $G$ defined by the adjacency list:

$1:\{2,3\}$ $2:\{1,3,4\}$ $3:\{1,2,4\}$ $4:\{2,3,5\}$ $5:\{4\}$

Determine whether $G$ contains an Eulerian trail or circuit.

Given the degree sequence $(3,3,2,2,2,2)$, determine whether there is a simple graph with this degree sequence and, if so, construct one.

Consider an electrical circuit where nodes $1,2,3,4$ are junctions and resistors connect nodes $(1,2),(2,3),(3,4),(4,1)$, and $(2,4)$. Represent this circuit as a simple graph and find the degree of each vertex.

Construct a simple graph with 7 vertices labeled $P,Q,R,S,T,U,V$ such that $\text{deg}(P)=3$, $\text{deg}(Q)=3$, $\text{deg}(R)=2$, $\text{deg}(S)=2$, $\text{deg}(T)=2$, $\text{deg}(U)=1$, and $\text{deg}(V)=1$. Provide the edge set $E$.

Given the simple graph $G$ with vertex set $V=\{A,B,C,D\}$ and edge set $E=\{\{A,B\},\{A,C\},\{B,C\},\{C,D\}\}$, determine the degree of each vertex and list the vertices adjacent to $C$.

Given a simple graph $G$ with vertices $1$ to $6$ and edge set $E=\{\{1,2\},\{2,3\},\{3,1\},\{4,5\},\{5,6\},\{6,4\}\}$. Is $G$ connected? Find all connected components and determine if $G$ contains any circuits.

Draw the corresponding simple graph and determine the degree of each vertex.

Given the adjacency matrix $$\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right),$$ list the adjacency list representation of the corresponding graph.