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