HLPL / VerTeX Modelling Language Documentation

← lessons

Graphs, degree, and three questions

Vertices, edges, the handshaking lemma, and the problems we will model.

Chapter: XIIb — Graph theory · lesson id gt-intro · theory lesson

---

A $graph$ is the barest description of "things and the connections between them": a set of $vertices$ and a set of $edges$ joining pairs of them. Roads between cities, friendships between people, dependencies between tasks — all graphs. This optional chapter takes three of the most famous questions you can ask about a graph — how few vertices touch every edge, how many vertices you can pick with no edge between them, and how many edges you can pick sharing no vertex — and writes each one as a small integer program you already know how to solve. One graph, three models, two clean theorems tying them together.

Notes

Definition (Graph). A $graph$ $G = (V, E)$ is a finite set of $vertices$ $V$ together with a set of $edges$ $E$, where each edge is an unordered pair ${u, v}$ of distinct vertices. Two vertices joined by an edge are $adjacent$; an edge and a vertex it contains are $incident$. Unless we say otherwise the graph is $undirected$ (edges have no direction) and $simple$ (no loops, no repeated edges).

Definition (Degree). The $degree$ $\deg(v)$ of a vertex $v$ is the number of edges incident to it — how many neighbours it has.

Our graph for the whole chapter

Every lesson here works on the same six-vertex graph so you can watch the three answers relate to one another. Its edges are ${1,2}, {1,3}, {1,4}, {2,5}, {4,5}, {5,6}$.

[network-graph diagram: The chapter graph: six vertices, six edges. Vertices 1 and 5 are the hubs (degree 3); vertices 3 and 6 are leaves (degree 1).]

The handshaking lemma

The first thing to know about degrees is that they are not free to be anything — they must add up correctly.

Theorem (Handshaking lemma). In any graph $G = (V, E)$, the sum of the vertex degrees equals twice the number of edges: $$\sum_{v \in V} \deg(v) = 2,|E|.$$ In particular, the number of vertices of odd degree is even.

Proof, step by step (Handshaking lemma).

1. Count the same thing two ways. What are we counting? Count the incidences — pairs $(v, e)$ where vertex $v$ is an endpoint of edge $e$.
2. Count incidences by summing over vertices. Each vertex $v$ contributes exactly $\deg(v)$ incidences, one per edge touching it. So the total is $\sum_{v \in V} \deg(v)$.
3. Now count the same incidences by summing over edges. Each edge has exactly two endpoints, so it contributes exactly $2$ incidences. With $|E|$ edges the total is $2,|E|$.
4. Conclude. Both count the same set, so $\sum_{v \in V} \deg(v) = 2,|E|$. The right side is even, so $|{v \in V : \deg(v) \text{ odd}}|$ is even. $\blacksquare$

Check it on our graph: the degrees are $\deg(1)=3,\ \deg(2)=2,\ \deg(3)=1,\ \deg(4)=2,\ \deg(5)=3,\ \deg(6)=1$. Their sum is $3+2+1+2+3+1 = 12 = 2 \times 6$, matching the six edges. Four vertices have odd degree — $1, 3, 5, 6$ — and four is even, exactly as the lemma requires.

Quick check. The handshaking lemma forces the number of odd-degree vertices to be even. Which degree sequence does it rule out on the spot?

• $(3, 2, 2, 2)$ ← correct
• $(3, 2, 2, 1)$
• $(2, 2, 2, 2)$

Bipartite graphs

Definition (Bipartite graph). A graph is $bipartite$ if its vertices can be split into two sets $A$ and $B$ so that every edge joins a vertex in $A$ to a vertex in $B$ — no edge stays inside $A$ or inside $B$. Equivalently (König, 1936): a graph is bipartite if and only if it contains no cycle of odd length.

Our chapter graph is bipartite: take $A = {1, 5}$ and $B = {2, 3, 4, 6}$ and check that all six edges cross between the two sides. That fact will matter in the last lesson — bipartite graphs make one of our two theorems especially sharp.

Three questions, three integer programs

1. $Vertex\ cover$ — fewest vertices touching every edge: $\min \sum_{v \in V} y_v$ subject to $y_u + y_v \geq 1 \ \forall {u,v} \in E$, $y_v \in {0,1} \ \forall v \in V$.
2. $Independent\ set$ — most vertices with no edge between them: $\max \sum_{v \in V} z_v$ subject to $z_u + z_v \leq 1 \ \forall {u,v} \in E$, $z_v \in {0,1} \ \forall v \in V$.
3. $Matching$ — most edges sharing no vertex: $\max \sum_{e \in E} x_e$ subject to $\sum_{e \in E : v \in e} x_e \leq 1 \ \forall v \in V$, $x_e \in {0,1} \ \forall e \in E$.

Notice cover and independent set are the same skeleton with the inequality flipped and the sense reversed. That is not a coincidence — it is the next lesson.

Recap.

• A graph is vertices plus edges; $\deg(v)$ counts a vertex's incident edges.
• Handshaking: $\sum_{v \in V} \deg(v) = 2|E|$, so odd-degree vertices come in an even number.
• Bipartite = 2-colourable = no odd cycle. Our chapter graph is bipartite.
• Vertex cover, independent set, and matching are each one small binary program.

Read this through MCP: read with path: "lessons/gt-intro", or resource hlpl://lessons/gt-intro.