# 3. Classroom tasks and solutions / Аудиторні задачі та розв'язання

> **Source of tasks.** The problems below are taken from the practical-class
> assignment for this topic (graph representation and colouring); only the wording
> has been translated to English. Each task collects several matrices or graphs, and
> **all of them are worked here in full**. Theory and notation are in
> [2method.md](2method.md); recall $\deg(v)$, $\Delta(G)$ (maximum degree),
> $\omega(G)$ (largest clique), $\chi$ (chromatic number), $\chi'$ (chromatic index).

## Задача 1 — draw the undirected graphs of the adjacency matrices

**Each matrix below is symmetric, so it describes an undirected graph. Draw it,
noting loops (diagonal) and parallel edges (entries $>1$), and read off the degrees.**

### (a)

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 0 | 1 | 0 | 1 |
| $B$ | 1 | 0 | 1 | 0 |
| $C$ | 0 | 1 | 0 | 1 |
| $D$ | 1 | 0 | 1 | 0 |

Zero diagonal (no loops) and every entry $0/1$ (simple). The $1$s give the edges
$AB,\ AD,\ BC,\ CD$ — a **4-cycle** $A\!-\!B\!-\!C\!-\!D\!-\!A$. Every row sums to
$2$, so $\deg A=\deg B=\deg C=\deg D=2$.

![Undirected graph of matrix (a): the 4-cycle A-B-C-D](img/t1a.png)

### (b)

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 1 | 0 | 1 | 1 |
| $B$ | 0 | 0 | 1 | 1 |
| $C$ | 1 | 1 | 0 | 1 |
| $D$ | 1 | 1 | 1 | 1 |

The diagonal has $a_{AA}=1$ and $a_{DD}=1$: a **loop at $A$** and a **loop at $D$**.
The off-diagonal $1$s give $AC,\ AD,\ BC,\ BD,\ CD$. Degrees (row sum, plus the
diagonal entry again so each loop counts twice):
$\deg A=3+1=4,\ \deg B=2,\ \deg C=3,\ \deg D=4+1=5$.

![Undirected graph of matrix (b): edges AC, AD, BC, BD, CD with loops at A and D](img/t1b.png)

### (c)

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 1 | 2 | 0 | 1 |
| $B$ | 2 | 0 | 3 | 0 |
| $C$ | 0 | 3 | 1 | 1 |
| $D$ | 1 | 0 | 1 | 0 |

A **multigraph**: $a_{AB}=2$ (two parallel edges $A\!=\!B$), $a_{BC}=3$ (three
parallel edges $B\!=\!C$), single edges $AD$ and $CD$, and **loops** at $A$
($a_{AA}=1$) and $C$ ($a_{CC}=1$). Degrees:
$\deg A=2(\text{loop})+2+1=5,\ \deg B=2+3=5,\ \deg C=2(\text{loop})+3+1=6,\ \deg D=1+1=2$.

![Undirected multigraph of the third matrix: double edge A-B, triple edge B-C, single edges A-D and C-D, loops at A and C](img/t1c.png)

## Задача 2 — draw the directed graphs of the adjacency matrices

**Each matrix below is not symmetric, so it describes a directed graph. Draw the
arcs (row $\to$ column), noting loops and multiplicities, and read off the in- and
out-degrees.**

### (a)

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 0 | 0 | 1 | 1 |
| $B$ | 0 | 0 | 1 | 0 |
| $C$ | 1 | 1 | 0 | 1 |
| $D$ | 1 | 1 | 1 | 0 |

Asymmetric, zero diagonal (no loops). The arcs are
$A\!\to\!C,\ A\!\to\!D,\ B\!\to\!C,\ C\!\to\!A,\ C\!\to\!B,\ C\!\to\!D,\
D\!\to\!A,\ D\!\to\!B,\ D\!\to\!C$. **Out-degrees** (row sums)
$\deg^{+}\!:A{=}2,B{=}1,C{=}3,D{=}3$; **in-degrees** (column sums)
$\deg^{-}\!:A{=}2,B{=}2,C{=}3,D{=}2$.

![Directed graph of matrix (a): nine arcs among A, B, C, D](img/t2a.png)

### (b)

| | $A$ | $B$ | $C$ | $D$ |
|:--:|:--:|:--:|:--:|:--:|
| $A$ | 0 | 2 | 3 | 0 |
| $B$ | 1 | 2 | 2 | 1 |
| $C$ | 2 | 1 | 1 | 0 |
| $D$ | 1 | 0 | 0 | 2 |

Asymmetric with a non-zero diagonal: **loops** at $B$ (two), $C$ (one), $D$ (two).
The arcs (with multiplicity) are $A\!\to\!B\,(2),\ A\!\to\!C\,(3),\ B\!\to\!A,\
B\!\to\!C\,(2),\ B\!\to\!D,\ C\!\to\!A\,(2),\ C\!\to\!B,\ D\!\to\!A$. A number beside
an arc is its multiplicity. **Out-degrees** (row sums)
$\deg^{+}\!:A{=}5,B{=}6,C{=}4,D{=}3$; **in-degrees** (column sums)
$\deg^{-}\!:A{=}4,B{=}5,C{=}6,D{=}3$ (each loop adds $1$ to both).

![Directed multigraph of matrix (b): arcs with multiplicities 2 and 3 and loops at B, C, D](img/t2b.png)

## Задача 3 — chromatic number and chromatic index

**For each graph find the chromatic number $\chi$ (colour the vertices) and the
chromatic index $\chi'$ (colour the edges). In every figure the vertices are already
painted with an optimal colouring.**

Throughout, the lower bound $\chi\ge\omega$ comes from a **triangle** (a clique of
size $3$), and the $\chi'$ lower bound is the maximum degree $\Delta$; a graph with
$\chi'=\Delta$ is **class 1**.

### Graph 1

![Graph 1 coloured with three colours; a 3-by-3 grid with two diagonals](img/cg1.png)

A $3\times3$ grid $a,b,c/d,e,f/g,h,k$ with the extra diagonals $b\!-\!d$ and
$f\!-\!h$, giving the triangles $b\,d\,e$ and $e\,f\,h$. Maximum degree $\Delta=4$
(at $b,d,e,f,h$).

- **$\chi=3$.** A triangle forces $\chi\ge3$; the three colour classes
  $\{b,f,g\},\ \{c,d,h\},\ \{a,e,k\}$ (shown red / blue / gold) are each independent,
  so $\chi\le3$. Hence $\boxed{\chi=3}$.
- **$\chi'=4$.** The four edges at $b$ need four colours, so $\chi'\ge\Delta=4$; a
  proper $4$-edge-colouring exists (class 1), so $\boxed{\chi'=4}$.

### Graph 2

![Graph 2 coloured with three colours; a multigraph on five vertices with two double edges](img/cg2.png)

A **multigraph** on $a,b,c,d,e$: double edges $a\!=\!d$ and $c\!=\!e$, plus
$ab,\ bc,\ bd,\ be,\ de$ — so $|E|=9$. The triangle $b\,d\,e$ gives $\chi\ge3$, and
$\Delta=4$ (at $b,d,e$).

- **$\chi=3$.** Parallel edges do not affect $\chi$; the classes
  $\{b\},\ \{c,d\},\ \{a,e\}$ are independent, so $\boxed{\chi=3}$.
- **$\chi'=5$.** Here $\Delta=4$, yet a colour class is a matching of at most
  $\lfloor5/2\rfloor=2$ edges, so at least $\lceil 9/2\rceil=5$ colours are needed:
  $\chi'\ge5$, and $5$ suffice. The parallel edges make it **class 2** with
  $\boxed{\chi'=5}$.

### Graph 3

![Graph 3 coloured with three colours; a six-cycle with a central hub and a pendant triangle](img/cg3.png)

A hexagon $c\!-\!a\!-\!b\!-\!e\!-\!h\!-\!g$ with a **hub** $d$ joined to all six, a
chord $c\!-\!e$ (drawn as the top arc), and a triangle $e\,f\,k$ on the right.
Maximum degree $\Delta=6$ (at $d$ and $e$).

- **$\chi=3$.** The hexagon with its chord is $2$-colourable, the hub $d$ takes a
  third colour, and the triangle $e\,f\,k$ reuses the same three: classes
  $\{a,e,g\},\ \{d,f\},\ \{b,c,h,k\}$. A triangle gives $\chi\ge3$, so
  $\boxed{\chi=3}$.
- **$\chi'=6$.** The six edges at $d$ (or $e$) need six colours, so $\chi'\ge6$; a
  proper $6$-edge-colouring exists (class 1), so $\boxed{\chi'=6}$.

### Graph 4

![Graph 4 coloured with three colours; ten vertices with e as a degree-six hub](img/cg4.png)

Ten vertices $a\ldots k$; the centre $e$ is joined to $a,b,c,g,h,i$, giving
$\Delta=6$, and there are many triangles ($a\,b\,e,\ b\,c\,e,\ a\,e\,h,\ c\,e\,h,\
e\,h\,i$).

- **$\chi=3$.** A triangle forces $\chi\ge3$; the classes
  $\{d,e,f\},\ \{a,c,g,i\},\ \{b,h,k\}$ are independent, so $\boxed{\chi=3}$.
- **$\chi'=6$.** The six edges at $e$ need six colours, so $\chi'\ge6$; a proper
  $6$-edge-colouring exists (class 1), so $\boxed{\chi'=6}$.

### Graph 5

![Graph 5 coloured with three colours; seventeen vertices with e as a degree-six hub](img/cg5.png)

Seventeen vertices; the hub $e$ is joined to $a,b,c,d,i,k$, so $\Delta=6$. The
triangles $a\,d\,e$ and $d\,e\,i$ give $\chi\ge3$.

- **$\chi=3$.** The classes $\{e,g,h,j,m,o,r\},\ \{a,b,c,i,k,l,n,p\},\ \{d,f\}$ are
  independent, so $\boxed{\chi=3}$.
- **$\chi'=6$.** The six edges at $e$ need six colours, so $\chi'\ge6$; a proper
  $6$-edge-colouring exists (class 1), so $\boxed{\chi'=6}$.