Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph: Visual walkthrough

This is the visual companion to the parent topic. Read that first for the vocabulary; here we slow the maths right down.

Step 1 — Draw the dots, name the counts

WHAT. Put down some dots. Each dot is a vertex. The whole collection of dots is the set $V$ . The whole collection of connecting lines is the set $E$ .

We give two counts their own letters so we never have to say the long words again:

$n = ∣ V ∣ m = ∣ E ∣$

$n$ ::: the little bars $∣ \cdot ∣$ mean "how many things are in this set", so $n$ = number of dots.
$m$ ::: same bars around $E$ , so $m$ = number of lines (edges).

WHY. Every edge question is really "given $n$ dots, how big can $m$ get?" So we must fix these two symbols before anything else.

PICTURE. Below: five dots labelled $A$ – $E$ , no lines yet. This is $n = 5$ , $m = 0$ — the empty starting canvas.

Figure — Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph

Step 2 — What is ONE edge allowed to be?

WHAT. An edge joins two dots. Before counting, we pin down two rules from the parent note:

No self-loop → the two dots must be different (a dot cannot connect to itself here).
Simple → between any pair, at most one line.

So a candidate edge is a pair of two distinct dots.

WHY. Counting edges = counting allowed pairs of dots. If we allowed self-loops or duplicates, the count would balloon — those cases get their own steps (7 and 8). We start with the clean simple case.

PICTURE. One green line between $A$ and $B$ : the atom we are about to count. Notice the red "forbidden" mark on the self-loop $A - A$ .

Step 3 — Count pairs the naïve way: $n \times (n - 1)$

WHAT. Build a pair in two moves.

$choices for 1st dot n \times choices for 2nd dot (n - 1) = n (n - 1)$

$n$ ::: pick the first endpoint — any of the $n$ dots is fine.
$n - 1$ ::: pick the second endpoint — any dot except the one already picked (that " $- 1$ " is the no-self-loop rule doing its job).

WHY. This "multiply the choices" idea is the basic counting move: independent decisions multiply. It answers how many ordered ways can I name two different dots?

PICTURE. A grid of all ordered pairs for $n = 5$ . The diagonal (same dot twice) is crossed out — that is why we get $5 \times 4 = 20$ cells, not $25$ .

Step 4 — Spot the double-count

WHAT. In an undirected graph the line $A - B$ is the same line as $B - A$ . But in Step 3 we counted " $A$ then $B$ " and " $B$ then $A$ " as two separate things.

${A, B} = {B, A} (same edge, counted twice)$

${\cdot}$ ::: curly braces mean an unordered set — order inside does not matter, so both writings are one object.

WHY. A handshake between two people is one handshake, even though both people are involved. Ordered counting listed each handshake from both sides.

PICTURE. The same grid as Step 3, now with matching cells paired by a violet arrow: $(A, B) \leftrightarrow (B, A)$ . Every off-diagonal cell has exactly one partner.

Step 5 — Divide by 2 → the master formula

WHAT. Since every undirected edge was counted exactly twice, halve the count:

$m_{m a x}^{undirected} = \frac{n ( n - 1 )}{2} = (2 n)$

$n (n - 1)$ ::: the ordered count from Step 3.
$\div 2$ ::: the double-count fix from Step 4.
$(2 n)$ ::: read "n choose 2" — a shorthand meaning the number of 2-element subsets of $n$ things, which is literally what we just computed.

WHY. This is the parent's headline formula, now earned rather than memorised. It is the edge count of the complete graph $K_n$ — the densest simple graph possible.

PICTURE. The complete graph on 5 dots. Count the green lines by hand: $10$ . And $(2 5) = \frac{5 \cdot 4}{2} = 10$ . ✓

Step 6 — The Handshaking Lemma falls out for free

WHAT. The degree $de g (v)$ of a dot is the number of line-ends touching it. Add degrees over all dots:

$\sum_{v \in V} de g (v) = 2 m$

$\sum_{v \in V}$ ::: "add up the following, once for each dot $v$ ".
$de g (v)$ ::: how many line-ends stick into dot $v$ .
$2 m$ ::: twice the number of edges.

WHY. Every edge has two ends. When we walk from dot to dot totting up how many ends we see, we meet each edge once at each of its two dots — so each edge contributes $+ 2$ to the grand total. Hence the sum equals $2 m$ , always.

Corollary (why it's useful): since the left side is $2 m$ (an even number), the dots with odd degree must pair up — the number of odd-degree vertices is always even. This is exactly the reasoning behind degree sequences.

PICTURE. A small graph where each edge is coloured, and each edge's two ends are ticked. Adding the ticks per dot gives the degrees; the grand total of ticks is visibly $2 m$ .

Step 7 — Edge case: allow self-loops

WHAT. Drop the "distinct dots" rule. Now an edge $(v, v)$ from a dot to itself is legal.

For max simple-edge counting this changes nothing (self-loops were excluded on purpose), but it changes degree: a self-loop adds $+ 2$ to that dot's degree (it has two ends, both at the same dot).

$de g_{with loop} (v) = (normal ends) + 2 \times (self-loops at v)$

WHY. The Handshaking Lemma must still read $\sum de g = 2 m$ . A self-loop is one edge with two ends — counting it as $+ 2$ keeps the "every edge contributes 2" bookkeeping exact.

PICTURE. A single dot $D$ with a self-loop; both ends of the loop are marked at $D$ , showing $de g (D) = 2$ from one edge.

Step 8 — Edge case: allow parallel edges (multigraph) & the tiny graphs

WHAT. Drop the "at most one line per pair" rule → a multigraph. Now $m$ has no upper bound at all: you can lay down 2, 5, 100 lines between the same two dots.

$m_{m a x}^{multigraph} = \infty$

Degenerate small graphs — always sanity-check these:

$n$	$\frac{n ( n - 1 )}{2}$	meaning
$0$	$0$	no dots, no edges
$1$	$0$	one lonely dot, nothing to connect to
$2$	$1$	one pair, one possible edge
$3$	$3$	a triangle

WHY. The formula must survive its smallest inputs. At $n = 1$ the factor $(n - 1) = 0$ kills the count — correct, a single dot cannot have a simple edge. At $n = 0$ everything is empty. A multigraph escapes the bound entirely, which is precisely why $\frac{n ( n - 1 )}{2}$ is a simple-graph statement only.

PICTURE. Left: two dots with three parallel violet lines ( $m = 3$ , unbounded idea). Right: the $n = 1$ lonely dot with the annotation $\frac{1 \cdot 0}{2} = 0$ .

The one-picture summary

Everything on one canvas: start with ordered pairs $n (n - 1)$ (directed answer), fold pairs together to halve into $\frac{n ( n - 1 )}{2}$ (undirected / $K_{n}$ ), and read the same edges as degree-ends summing to $2 m$ (handshake). The three big results are three views of one counting picture.

Recall Feynman retelling — say it to a 12-year-old

Put down some dots. To make a line I pick a dot ( $n$ ways), then a different dot ( $n - 1$ ways) — that's $n (n - 1)$ ways to name a line. But if arrows don't matter, " $A$ then $B$ " is the very same line as " $B$ then $A$ ", so I counted every line twice — divide by 2, giving $\frac{n ( n - 1 )}{2}$ . That's the most lines a neat ("simple") drawing can have. Now flip it around: each line has two ends, so if I count all the ends poking into every dot, I've counted every line twice again — so all those degree-numbers add up to $2 m$ . A loop from a dot back to itself pokes both its ends into the same dot, so it counts as $2$ . And if I'm allowed to draw a bundle of lines between the same two dots (a multigraph), then there's no limit at all. That's the whole story — the same "two ends, count twice" idea, seen from three sides.

Where this leads

The count $\frac{n ( n - 1 )}{2}$ vs an actual small $m$ is the whole story of dense vs sparse graphs.
How you store those $m$ edges is adjacency list vs matrix — and note the " $2 m$ entries" warning for undirected lists comes straight from Step 6.
Once you can walk edges: BFS, Dijkstra, Topological sort, and the acyclic special case, trees.

Flashcards

Max edges of a simple undirected graph on

n

vertices, and why divide by 2?

\frac{n ( n - 1 )}{2}

; because

{u, v}

and

{v, u}

are the same undirected edge, so ordered count

n (n - 1)

was doubled.

Max edges of a simple directed graph (no self-loops) on

n

vertices?

n (n - 1)

— no division, since

(u, v) \neq = (v, u)

State the Handshaking Lemma and the one-line reason.

\sum_{v} de g (v) = 2 m

; each edge has two ends, counted once at each endpoint.

Why does a self-loop add 2 to a vertex's degree?

It is one edge with both ends at the same vertex, so both ends are counted there.

What is

\frac{n ( n - 1 )}{2}

n = 1

and what does it mean?

0

— a single lonely vertex has no other vertex to connect to.

Why is max edges of a multigraph unbounded?

Parallel edges are allowed, so you can place arbitrarily many edges between the same pair.