Question 1.2.2 Let $G$ be the multigraph shown below. Find $V(G)$, $E(G)$, $v(G)$, and $e(G)$.

Solution

$$V(G) = \{u, v, w, x, y\} \\ E(G) = \{uv, uw, e_1, e_2, vx, wy, xy\} \\ v(G) = 5 \\ e(G) = 7$$

---

Question 1.2.3. Let $H$ be the graph with $V(H) = \{a,b,c,x,y,z\}$ and $E(H) = \{ab, ay, bx, by, cx, cz, xz, yz\}$. Find $v(H)$ and $e(H)$, and draw a diagram of $H$.

Solution
$v(H) = 6$
$e(H) = 8$

---

Question 1.2.4 Let $G$ be the multigraph shown below.

$(i)\>$ Find $A(G)$
$(ii)\>$ Is $A(G)$ symmetric (i.e., $(i,j)$-entry = $(j,i)$=entry)?
$(iii)\>$ What is the sum of the values of the entries in each row (respectively, column)?
$(iv)\>$ What is your interpretation of the 'sum' obtained in $(iii)$?

Solution

$(i)$

$$A(G) = \begin{pmatrix} 0 & 1 & 3 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 3 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \end{pmatrix}$$

$(ii)\>$ Yes, $A(G)$ is symmetric.
$(iii)\>$ $5, 2, 6, 2, 3$
$(iv)\>$ The sum of the values of the entries in each row corresponds to the total number of edges that vertex is incident with.

---

Question 1.2.5 The adjacency matrix of a multigraph $G$ is given below:

$$A = \begin{pmatrix} 0 & 2 & 1 & 0 & 1 \\ 2 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 3 & 2 \\ 0 & 0 & 3 & 0 & 0 \\ 1 & 0 & 2 & 0 & 0 \\ \end{pmatrix}$$

Draw a diagram of $G$
Solution

---

Exercise 1.2

(1) Let $G$ be the multigraph representing the following diagram. Determine $V(G)$, $E(G)$, $v(G)$, and $e(G)$. Is $G$ a simple graph?

Solution

$$V(G) = \{w, m, n, x, y, u, v, z\} \\ E(G) = \{ wu, wx, my, xu, xv, xz, yv, yz, uv \} \\ v(G) = 8\\ e(G) = 9$$

$G$ is a simple graph.

---

(2) Draw the graph $G$ modeling the flight connectivity between twelve capital cities with the following vertex set $V(G)$ and edge set $E(G)$.

$$\begin{aligned} V(G) = &\{ \text{Asuncion}, \text{Beijing}, \text{Canberra}, \text{Dili}, \text{Havana}, \text{Kuala Lumpur}, \\ &\text{London}, \text{Nairobi}, \text{Phnom Penh}, \text{Singapore}, \text{Wellington}, \text{Zagreb} \}. \\ E(G) = &\{\text{Asuncion-London}, \text{Asuncion-Havana}, \text{Beijing-Canberra} \\ &\text{Beijing-Kuala Lumpur}, \text{Beiijng-London}, \text{Beijing-Singapore} \\ &\text{Beijing-Phnom Penh}, \text{Dili-Kuala Lumpur}, \text{Dili-Singapore} \\ &\text{Dili-Canberra}, \text{Havana-London}, \text{London-Wellington} \\ &\text{Kuala Lumpur-London}, \text{Kuala Lumpur-Phnom Penh} \\ &\text{Kuala Lumpur-Singapore}, \text{Kuala Lumpur-Wellington} \\ &\text{London-Nairobi}, \text{Phnom Penh-Singapore}, \text{London-Singapore} \\ &\text{London-Zagreb}, \text{Singapore-Wellington}, \text{Havana-Nairobi} \}. \end{aligned}$$

(Note that you may use A to represent Asuncion, B to represent Beijing, C to represent Canberra, etc. )

Solution

---

(3) Define a graph $G$ such that $V(G) = \{ 2, 3, 4, 5, 11, 12, 13, 14 \}$ and two vertices $s$ and $t$ are adjacent if and only if $\text{gcd}\{s, t\} = 1$. Draw a diagram of $G$ and find its size $e(G)$.

Solution
First we draw the graph $G$

To find $e(G)$ we simply count all the edges.

We conclude that $e(G) = 20$.

---

(4) The following diagram is a map of the road system in a town. Draw a multigraph to model the road system, using a vertex to represent a junction and an edge to represent a road joining two junctions.

Solution
Start by labeling all the junctions

Here's the graph

---

(5) Let $G$ be a graph with $V(G) = \{1, 2, \cdots, 10\}$, such that two numbers $i$ and $j$ in $V(G)$ are adjacent if and only if $|i - j| \leq 3$. Draw the graph $G$ and determine $e(G)$.

Solution
First draw the graph $G$. Note that the author uses the term "graph" to refer to a simple graph.

Next label all the edges

$$e(G) = 24$$

---

(6) Let $G$ be a graph with $V(G) = \{1, 2, \cdots, 10\}$, such that two numbers $i$ and $j$ in $V(G)$ are adjacent if and only if $i + j$ is a multiple of $4$. Draw the graph $G$ and determine $e(G)$.

Solution

First we draw $G$

Next label the edges

$$e(G) = 9$$

---

(7) Let $G$ be a graph with $V(G) = \{1, 2, \cdots, 10\}$, such that two numbers $i$ and $j$ in $V(G)$ are adjacent if and only if $i \times j$ is a multiple of $10$. Draw the graph $G$ and determine $e(G)$.

Solution

First we draw the graph $G$

Next count the edges

$$e(G) = 13$$

---

(8) Find the adjacency matrix of the following graph $G$.

Solution

$$A(G) = \begin{pmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}$$

---

(9) The adjacency matrix of a multigraph $G$ is shown below:

$$\begin{pmatrix} 0 & 1 & 0 & 2 & 3 \\ 1 & 0 & 1 & 2 & 2 \\ 0 & 1 & 0 & 1 & 1 \\ 2 & 2 & 1 & 0 & 1 \\ 3 & 2 & 1 & 1 & 0 \end{pmatrix}$$

Draw a diagram of $G$

Solution

---

(10) Four teams of three specialist soldiers each (a scout, a signaler and a sniper) are to be sent into enemy territory. However, some of the soldiers cannot work will with some others. The following table shows the soldiers, their specializations and who they cannot work with.

Solider	Specialization	Cannot cooperate with
1	Scout	5, 7, 10
2	Scout	-
3	Scout	5, 6, 8, 9, 11
4	Scout	8, 12
5	Signaler	1, 3, 9
6	Signaler	3, 10, 11
7	Signaler	1, 9, 12
8	Signaler	3, 4, 9, 10
9	Sniper	3, 5, 7, 8
10	Sniper	1, 6, 8
11	Sniper	3, 6
12	Sniper	4, 7

(i) Draw a multigraph to model the situation so that we may see how to form 3-man teams such that each specialization is represented and every member of the team can work with every other. State clearly what the vertices represent and under what condition(s) two vertices are joined by an edge.

(ii) Can you form four 3-man teams such that each specialization if represented and all members of the teams can work with one another?

Solution
(i) Let each vertex represent a solider, and join two vertices by an edge if they can work together. This means that they must be of different specializations and not be on the "cannot cooperate with" section.

(ii) From the diagram we can clearly see four 3-man teams that work:

$$\{1, 6, 9\}, \{2, 8, 12\}, \{4, 5, 11\}, \{3, 7, 10\}$$

$$\\$$