RevisionDojo

Question 1

A simple graph $G$ has adjacency matrix

\begin{pmatrix} 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{pmatrix}

Determine the number of connected components and identify them.

[3]

Question 2

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.

[3]

Question 3

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.

[6]

Question 4

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.

[8]

Question 5

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.

[4]

Question 6

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.

[6]

Question 7

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.

[4]

Question 8

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$ .

[3]

Question 9

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$ .

[3]

Question 10

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.

[4]

Question 11

The following table represents the friendship strengths between five people $A$ , $B$ , $C$ , $D$ , and $E$ . A friendship strength $\ge 6$ defines an edge in a simple graph representing their social network.

\begin{array}{c|ccccc} & A & B & C & D & E\\ \hline A & - & 7 & 5 & 6 & 4 \\ B & 7 & - & 8 & 3 & 6 \\ C & 5 & 8 & - & 6 & 2 \\ D & 6 & 3 & 6 & - & 7 \\ E & 4 & 6 & 2 & 7 & - \end{array}

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

[4]

Question 12

Given the adjacency matrix

\begin{pmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 \end{pmatrix},

list the adjacency list representation of the corresponding graph.

[2]

Question Type 1: Determining properties of a given simple graph Exercises