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. For fuller treatment see Lecture 10, §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.)
• 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$)

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.

Practical/Practical5/2method.md · 6.4 KB · updated 2026-07-31 21:51