# Laboratory Work 6 — Graph Theory Basics

> Sixth laboratory work of **Computer Discrete Mathematics**. You implement the
> core operations on **graphs**: vertex degrees and the handshaking theorem, the
> **adjacency** and **incidence** matrices, path finding, subgraph testing,
> isomorphism, and the discovery of circuits, walks, and trails.

## At a glance

| | |
|---|---|
| **Topic** | Graphs: degree, matrix representations, paths, subgraphs, isomorphism, circuits, walks & trails |
| **Prerequisite lectures** | [L10 — Graph theory (basics)](../../Lectures/CDM-L10.md) |
| **Deliverable** | Source code + report (see [5report.md](5report.md)) |
| **Grading** | Banded: Easy 60–74 / Medium 75–89 / Hard 90–100 (see [4task.md](4task.md)) |

## Contents

| # | Part | File |
|:--:|---|---|
| 1 | Objective | [1purpose.md](1purpose.md) |
| 2 | Methodical guidelines (theory & algorithms) | [2method.md](2method.md) |
| 4 | Task and order of execution | [4task.md](4task.md) |
| 5 | Report contents | [5report.md](5report.md) |
| 6 | Control questions | [6questions.md](6questions.md) |

## Conventions

- **Language** — source code and the report are in **English**.
- **Implement it yourself — no built-in shortcuts.** Do not call a library or
  built-in that performs the core task for you (e.g. no `HashSet`/`set()`/`Set`
  for sets, no library graph/relation type, no `math.gcd`, no `eval`). Build the
  mechanism from basic primitives — arrays/lists, loops, arithmetic, strings.
- **Deliverable** — submit the source code **and** a report structured as in
  [5report.md](5report.md); the code must reproduce the example outputs in
  [4task.md](4task.md).
- **Self-contained theory** — everything needed is in [2method.md](2method.md);
  no external material is required.

## Summary

A **graph** models a set of objects (**vertices**) and the connections between
them (**edges**). This work covers the foundations: measuring how connected a
vertex is (its **degree**) and the handshaking theorem that ties degrees to the
number of edges; the two standard matrix encodings (**adjacency** and
**incidence**); moving through a graph via **walks, trails, paths**, and
**circuits**; and comparing graphs through the **subgraph** and **isomorphism**
relations. The tasks are grouped into three difficulty bands.