---
title: What a Graph Is, and How to Notice One
summary: Vertices, edges, and the modelling habit that turns a scary statement into a graph problem.
difficulty: easy
tags: [modelling, definitions]
---

A **graph** is a pair $G = (V, E)$: a set of *vertices* and a set of *edges*, where each edge is a 2-element subset of $V$.
That is the entire definition. Everything else in this chapter is bookkeeping.

:::definition label="Size, order, degree"
The **order** is $n = |V|$, the **size** is $m = |E|$. The **degree** $\deg(v)$ of a vertex is the number of edges touching it; a vertex with $\deg(v) = 0$ is *isolated*.
:::

## The handshaking lemma
:::theorem title="Handshaking"
$\sum_{v \in V} \deg(v) = 2m$. In particular, the number of odd-degree vertices is even.
:::

:::proof
Sum degrees by *counting edges*: each edge contributes exactly 1 to each of its two endpoints, hence 2 to the total.
:::

:::demo id="graph-explorer"
:::

## Figure
:::figure src="Apple_Pineapple.svg" caption="Two vertices, one edge: the smallest interesting graph."
:::