# Practical Work 5 — Graphs: Representation and Colouring

> Fifth practical class of **Computer Discrete Mathematics**. Working **by hand**,
> you move between a graph and its **adjacency matrix** (undirected and directed),
> and you colour graphs — finding the **chromatic number** $\chi$ (vertices) and the
> **chromatic index** $\chi'$ (edges).

## At a glance

| | |
|---|---|
| **Topic** | Adjacency matrix (undirected / directed, loops, multigraphs); drawing a graph from its matrix; proper vertex and edge colouring; chromatic number and index; Vizing class |
| **Prerequisite lectures** | [L10 — Graph theory (basics)](../../Lectures/CDM-L10.md) (representations §10.6, colouring §10.12) |
| **Mode** | In-class problem solving — pen and paper, no computer |
| **Deliverable** | Worked solutions to the tasks in [3classroom.md](3classroom.md) |

## Contents

| # | Part | File |
|:--:|---|---|
| 1 | Objective | [1purpose.md](1purpose.md) |
| 2 | Methodical guidelines (self-contained theory) | [2method.md](2method.md) |
| 3 | Classroom tasks **with solutions** | [3classroom.md](3classroom.md) |
| 6 | Control questions | [6questions.md](6questions.md) |

## Conventions

- **Language** — all work is written in **English**.
- **By hand.** Read each matrix, draw the graph, and colour it directly; show the
  colour of every vertex (or edge) and the group each belongs to.
- **Adjacency-matrix convention.** The entry $a_{ij}$ is the **number of edges**
  (undirected) or **arcs** (directed) between $v_i$ and $v_j$; a **diagonal** entry
  $a_{ii}$ is the **number of loops** at $v_i$. (Some texts, including
  [L10](../../Lectures/CDM-L10.md), instead count each loop as $2$ on
  the diagonal; this worksheet counts loops once, matching its data.)
- **Notation is fixed and self-contained.** $\deg(v)$ is the degree; $\Delta(G)$ the
  maximum degree; $\omega(G)$ the largest clique; $\chi(G)$ the chromatic number and
  $\chi'(G)$ the chromatic index. All are defined in [2method.md](2method.md).
- **Every task has a full solution.** [3classroom.md](3classroom.md) gives each task
  together with a complete worked answer, including the drawn graph and its colouring.

## Summary

A graph can be stored as a table of numbers — its **adjacency matrix** — and drawn
back from that table; the two views are interchangeable, and the matrix instantly
shows whether the graph is **directed** (asymmetric), has **loops** (non-zero
diagonal), or **parallel edges** (entries above $1$). The second theme is
**colouring**: paint the **vertices** so neighbours differ (the fewest colours is
the **chromatic number** $\chi$), or the **edges** so those meeting at a vertex
differ (the fewest is the **chromatic index** $\chi'$). Colouring turns real
conflict problems — timetabling, register allocation, frequency assignment — into a
single question, *how few colours are enough?*, bounded below by the biggest clique
and the maximum degree and, for edges, pinned by **Vizing's theorem** to just two
possible values.