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; 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) #

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

(b) #

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

(c) #

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

Задача 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) #

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

(b) #

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

Задача 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 #

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 #

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 #

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 #

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 #

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

Practical/Practical5/3classroom.md · 7.3 KB · updated 2026-07-31 21:14