6. Control questions and tasks / Контрольні запитання і завдання #

Adjacency matrices #

1. Define the adjacency matrix of a graph. What does the entry $a_{ij}$ mean when it is $0$, when it is $1$, and when it is $3$?
2. How do you tell from the matrix alone whether a graph is directed or undirected? Where do loops appear?
3. For an undirected graph, how is $\deg(v_i)$ read from the matrix? For a digraph, which sum gives the out-degree and which the in-degree?
4. Write the adjacency matrix of the $4$-cycle $A\!-\!B\!-\!C\!-\!D\!-\!A$, then add a loop at $A$ and a second edge $B\!=\!C$; show how each change alters the matrix.
5. Draw the undirected graph of $\begin{pmatrix}0&1&1\\1&0&2\\1&2&1\end{pmatrix}$ (vertices $x,y,z$) and give the degree of each vertex.

Vertex colouring and the chromatic number #

6. Define a proper vertex colouring and the chromatic number $\chi(G)$. Why do parallel edges not change $\chi$, while a loop makes proper colouring impossible?
7. State the clique lower bound and the greedy upper bound for $\chi$. What is $\chi(K_n)$?
8. Prove that $\chi(G)\le 2$ iff $G$ is bipartite iff $G$ has no odd cycle. What are $\chi(C_{2k})$ and $\chi(C_{2k+1})$?
9. To show $\chi(G)=3$ you must argue two things — which two? (This is exactly how Graphs 1–5 of Задача 3 are settled.)

Edge colouring and the chromatic index #

10. Define a proper edge colouring and the chromatic index $\chi'(G)$. Why is each colour class a matching?
11. State Vizing’s theorem. What do class 1 and class 2 mean? Give the $\chi'$ of Graph 1 (Задача 3) and say which class it is.
12. Graph 2 of Задача 3 has $\Delta=4$ but $\chi'=5$. Using the counting bound $\chi'\ge\lceil |E|/\lfloor n/2\rfloor\rceil$, explain why four colours cannot suffice for its $9$ edges on $5$ vertices.

Practical/Practical5/6questions.md · 1.9 KB · updated 2026-07-31 21:14