# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it collects the theory needed for the theme —
graphs and their adjacency matrices, and vertex/edge colouring — together with the
techniques used to solve the tasks in [3classroom.md](3classroom.md). For fuller
treatment see [Lecture 10](../../Lectures/CDM-L10.md), §10.6–10.12.

## 2.1 Graphs, degrees, and kinds of edge

A **graph** $G=(V,E)$ is a set of **vertices** $V$ and a set of **edges** $E$, each
edge joining two vertices. The kinds we meet in this class:

- an **undirected** edge $\{u,v\}$ has no direction; a **directed** edge (an **arc**)
  $(u,v)$ points from $u$ to $v$;
- a **loop** is an edge from a vertex to **itself**;
- **parallel** (or **multiple**) edges join the **same** pair of vertices; a graph
  that allows loops and parallel edges is a **multigraph**. A graph with neither is
  **simple**.

The **degree** $\deg(v)$ is the number of edge-ends at $v$ (a loop counts **twice**).
In a digraph the **out-degree** $\deg^{+}(v)$ counts arcs leaving $v$ and the
**in-degree** $\deg^{-}(v)$ counts arcs entering. The largest degree in $G$ is
$\Delta(G)$; a set of pairwise-adjacent vertices is a **clique**, and the size of the
largest one is $\omega(G)$.

## 2.2 The adjacency matrix

Number the vertices $v_1,\dots,v_n$. The **adjacency matrix** $A=[a_{ij}]$ is the
$n\times n$ table with

$$a_{ij} = \bigl(\text{number of edges/arcs between } v_i \text{ and } v_j\bigr).$$

Reading a matrix, four features are immediate:

- **Directed or undirected?** For an **undirected** graph $A$ is **symmetric**
  ($a_{ij}=a_{ji}$): the picture above the diagonal mirrors the picture below. If
  $A$ is **not** symmetric the graph is **directed**.
- **Loops** sit on the **diagonal**: $a_{ii}$ is the number of loops at $v_i$. (Here
  a loop counts **once** on the diagonal; some texts count it as $2$ — see the note
  in [main.md](main.md).)
- **Parallel edges** show up as entries **greater than $1$**: $a_{ij}=3$ means three
  edges between $v_i$ and $v_j$.
- **Degrees.** For an undirected graph the **$i$-th row sum equals $\deg(v_i)$** (a
  loop, counted once in $a_{ii}$, must be added a second time to match the
  "loop counts twice" rule for degree). For a digraph the **row sum** is the
  out-degree $\deg^{+}(v_i)$ and the **column sum** is the in-degree $\deg^{-}(v_i)$.

*Example.* The symmetric matrix (rows/cols $A,B,C,D$)

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

is symmetric with zero diagonal, so it is an **undirected**, loop-free, simple
graph; the $1$s give the edges $AB, AD, BC, CD$ — a $4$-cycle.

## 2.3 Drawing a graph from its adjacency matrix

1. **Place** the $n$ vertices (a convenient layout — a circle or a square — keeps
   edges from crossing needlessly).
2. **Decide directed vs. undirected** from the symmetry of $A$.
3. **Off-diagonal entries:** for each $a_{ij}$ (with $i<j$ if undirected) draw
   $a_{ij}$ edges between $v_i$ and $v_j$ — a single line, or parallel lines when the
   entry exceeds $1$. For a **digraph** draw an **arrow** $v_i\to v_j$ for $a_{ij}$
   and a separate arrow $v_j\to v_i$ for $a_{ji}$.
4. **Diagonal entries:** draw $a_{ii}$ **loops** at $v_i$.
5. **Check** by reading the degrees back off the rows (and columns, for a digraph).

## 2.4 Vertex colouring and the chromatic number

A **proper vertex colouring** assigns a colour to every vertex so that **adjacent
vertices get different colours**. The **chromatic number** $\chi(G)$ is the fewest
colours a proper colouring can use. (Loops make proper colouring impossible, and
parallel edges do not matter — so $\chi$ depends only on the **simple** graph
underneath.)

Two bounds trap $\chi$:

- **Lower bound — a clique.** In a clique of size $k$ all $k$ vertices are mutually
  adjacent, so they need $k$ distinct colours: $\ \chi(G)\ge\omega(G)$. In
  particular a single **triangle** forces $\chi\ge 3$.
- **Upper bound — greedy.** Colouring vertices one at a time, each has at most
  $\Delta$ already-coloured neighbours, so one of $\Delta+1$ colours is always free:
  $\ \chi(G)\le\Delta(G)+1$.

Landmark values: $\chi=1$ iff there are no edges; $\chi(K_n)=n$; and $\chi(G)\le 2$
**iff** $G$ is **bipartite** **iff** $G$ has **no odd cycle**. Hence an even cycle
has $\chi=2$ and an odd cycle has $\chi=3$. To **prove** $\chi(G)=k$: exhibit a
$k$-colouring (so $\chi\le k$) **and** a reason it cannot be done with fewer, usually
a clique of size $k$ (so $\chi\ge k$).

## 2.5 Edge colouring and the chromatic index

A **proper edge colouring** colours the edges so that **edges sharing a vertex get
different colours**; the fewest colours is the **chromatic index** $\chi'(G)$.
Equivalently, each colour class is a **matching** (a set of edges with no common
endpoint).

- **Lower bound — the busiest vertex.** The $\Delta$ edges at a maximum-degree vertex
  pairwise meet there, so all need different colours: $\ \chi'(G)\ge\Delta(G)$.
- **Vizing's theorem.** For a **simple** graph, $\ \chi'(G)\in\{\Delta,\ \Delta+1\}$.
  Graphs meeting the lower value are **class 1**; those needing $\Delta+1$ are
  **class 2**. (For a **multigraph** the top can rise: $\chi'\le\Delta+\mu$, where
  $\mu$ is the largest edge multiplicity.)
- **A counting bound.** A colour class is a matching, so it has at most
  $\lfloor n/2\rfloor$ edges; hence $\ \chi'(G)\ge\lceil |E|/\lfloor n/2\rfloor\rceil$.
  This is what pushes a small, edge-heavy multigraph above $\Delta$.

To **prove** $\chi'(G)=k$: exhibit a $k$-edge-colouring and give a reason fewer is
impossible ($\Delta$, or the counting bound).

## 2.6 Working checklist

- **Matrix → graph:** check symmetry (directed or not); place the vertices; draw
  off-diagonal edges (parallel lines / arrows for entries $>1$); add diagonal loops;
  verify degrees against row (and column) sums.
- **Chromatic number $\chi$:** find the largest clique for a **lower** bound; colour
  greedily (hardest vertices first) for an **upper** bound; when the two meet you are
  done. A triangle already forces $\chi\ge 3$; no odd cycle means $\chi\le 2$.
- **Chromatic index $\chi'$:** start at $\Delta$; try to build a $\Delta$-edge-colouring
  (class 1). If it is forced higher — by Vizing to $\Delta+1$, or by the counting
  bound $\lceil |E|/\lfloor n/2\rfloor\rceil$ for a dense multigraph — say so.