Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph: Worked examples

You have met the four switches (Direction, Weight, Self-loop, Parallel) in the parent note. Knowing the definitions is not the same as being able to classify and count in every situation. This page hunts down every case — every switch combination, the degenerate graphs (no edges, one vertex, everything self-loops), the limiting sizes, a word problem, and an exam twist — and works each one out from zero.

The scenario matrix

Before working examples, let us list every case class this topic can throw at you. Each row is a "type of situation"; the last column names the worked example that lands in that cell.

#	Case class	What makes it tricky	Covered by
1	Undirected + simple, counting	divide-by-2 handshake	Ex 1
2	Directed + simple, counting	do not divide by 2	Ex 2
3	Multigraph (parallel edges) classify + degree	duplicates count separately	Ex 3
4	Self-loops present	a loop adds +2 to degree	Ex 4
5	Directed in-degree / out-degree split	two degrees per vertex	Ex 5
6	Weighted, real-world shortest path	picking BFS vs Dijkstra	Ex 6
7	Degenerate: empty edge set / single vertex / self-loops only	$m = 0$ , $n = 1$ , limiting behaviour	Ex 7
8	Limiting size: densest possible (complete graph)	$m$ hits its maximum	Ex 8
9	Word problem mixing switches	translate English → $(V, E)$	Ex 9
10	Exam twist: "is this degree sequence possible?"	Handshaking parity check	Ex 10

Every switch combination (directed?, weighted?, self-loop?, parallel?) and every degenerate/limiting input appears in at least one row. Now we clear the grid.

First, the tools we will reuse

WHY these three and not others? Almost every counting question reduces to one of them. "How dense can it get?" → the max-edge formulas. "Do these degrees add up?" → the handshake. If you internalise why the 2 appears (an edge touches two endpoints; an unordered pair is one handshake between two people) you never memorise — you re-derive. The link Complete graph $K_n$ and dense vs sparse graphs pushes the first formula further; Handshaking lemma and degree sequences pushes the third.

Look at the figure above: the left panel is one undirected edge — one handshake, touched at two dots (blue). The right panel splits it into two directed arcs (orange). Same picture, but the edge count differs: 1 vs 2. Hold this image; it explains every divide-by-2 below.

Cell 1 — Undirected + simple, counting max edges

Worked example Example 1 (Cell 1)

A group of $n = 6$ people. Everyone shakes hands with everyone else exactly once. Model as a simple undirected graph. How many edges (handshakes)?

Forecast: Guess before reading — is it $6 \times 5 = 30$ , or half of that? Write your guess.

Each handshake is an unordered pair of two distinct people. Why this step? "Simple" forbids duplicates and self-loops, so each pair is counted at most once and nobody shakes their own hand.
Count ordered picks first: first person $6$ ways, second (different) $5$ ways $\Rightarrow 6 \cdot 5 = 30$ . Why? Easier to count ordered, then correct.
Divide by 2. Why? The pick "Alice then Bob" and "Bob then Alice" are the same handshake — look at the left panel of the figure, one line, two endpoints. So $30/2 = 15$ .

$m_{m a x} = (2 6) = \frac{6 \cdot 5}{2} = 15$

Verify: Plug $n = 6$ into $\frac{n ( n - 1 )}{2} = \frac{6 \cdot 5}{2} = 15$ . ✓ Sanity: 15 < 30, and the "/2" matched the mnemonic "a handshake needs two people but is one handshake".

Cell 2 — Directed + simple, counting

Cell 3 — Multigraph (parallel edges), classify + degree

Cell 4 — Self-loops present

Cell 5 — Directed: in-degree vs out-degree

Cell 6 — Weighted, real-world: which algorithm?

Worked example Example 6 (Cell 6)

Four cities with roads (undirected, weighted by km): $A - B : 4$ , $A - C : 1$ , $C - B : 2$ , $B - D : 5$ , $C - D : 8$ . Find the shortest distance from $A$ to $D$ , and say which algorithm you'd use.

Forecast: The direct-looking route $A - B - D$ is $4 + 5$ . Is there something cheaper?

Weights are non-negative distances, and we want minimum total cost. Why this fixes the tool? Non-negative weights + shortest path ⇒ Dijkstra's algorithm. (Plain BFS — breadth first search would be wrong here because it ignores the numbers, treating every road as length 1.)
Enumerate simple routes $A \to D$ :
- $A - B - D = 4 + 5 = 9$
- $A - C - B - D = 1 + 2 + 5 = 8$
- $A - C - D = 1 + 8 = 9$ Why enumerate? Small graph — direct check confirms Dijkstra's answer.
Take the minimum: $min (9, 8, 9) = 8$ , via $A - C - B - D$ .

Verify: The green path in the figure sums $1 + 2 + 5 = 8$ , beating the "obvious" $A - B - D = 9$ . ✓ Units: kilometres throughout — consistent.

Cell 7 — Degenerate inputs (the cases people forget)

Worked example Example 7 (Cell 7 — three degenerate sub-cases)

Handle each edge case with the formulas.

(a) Empty edge set: $n = 4$ , $m = 0$ . Degrees?

No edges touch anything, so every $de g (v) = 0$ . Why? Degree counts touching edges; there are none.
Verify: $\sum de g = 0 = 2 \cdot 0 = 2 m$ . ✓

(b) Single vertex, simple undirected: $n = 1$ . Max edges?

$(2 1) = \frac{1 \cdot 0}{2} = 0$ . Why zero? A simple graph forbids self-loops, and there is no other vertex to connect to — a lonely dot.
Verify: $\frac{1 \cdot ( 1 - 1 )}{2} = 0$ . ✓ Limiting sanity: the formula gracefully returns $0$ , no special-casing needed.

(c) All self-loops, multigraph: $n = 3$ , each vertex has exactly one self-loop, no other edges. Degrees and $m$ ?

$m = 3$ (three loops). Each loop adds $+ 2$ to its vertex, so every $de g = 2$ .
Verify: $\sum de g = 2 + 2 + 2 = 6 = 2 \cdot 3 = 2 m$ . ✓ Even a graph made only of loops obeys handshaking.

Cell 8 — Limiting size: the densest graph

Cell 9 — Word problem mixing switches

Worked example Example 9 (Cell 9)

"A one-way road network of $5$ intersections. Between intersection $2$ and intersection $3$ there are two separate one-way alleys, both $2 \to 3$ , with tolls $1 and $3. Other one-way roads: $1 \to 2$ ($5), $3 \to 4$ ($2), $4 \to 5$ ($4), $2 \to 4$ ($7)." Classify all four switches, then find the cheapest $1 \to 5$ trip.

Forecast: Which switches are ON here?

Directed? Yes — every road is one-way (ordered pairs). Weighted? Yes — tolls. Self-loops? No road goes to its own intersection. Parallel edges? Yes — two $2 \to 3$ alleys ⇒ directed weighted multigraph. Why classify first? It tells you the model: parallel arcs must both be stored (adjacency list has both, see Graph representations — adjacency list vs matrix).
Cheapest routes $1 \to 5$ : the only path to $5$ is via $4 \to 5$ . Reach $4$ either by $2 \to 4$ ($7) or $3 \to 4$ ($2) after $2 \to 3$ (cheapest alley $1).
- $1 \to 2 \to 3 \to 4 \to 5 = 5 + 1 + 2 + 4 = 12$
- $1 \to 2 \to 4 \to 5 = 5 + 7 + 4 = 16$ Why take the $1 alley? Among parallel $2 \to 3$ arcs, shortest-path always uses the cheaper — the $3 one is dominated.
Minimum: $min (12, 16) = 12$ .

Verify: $5 + 1 + 2 + 4 = 12$ and $5 + 7 + 4 = 16$ ; cheapest $= 12$ via the $1 alley. ✓ Units: dollars.

Cell 10 — Exam twist: is a degree sequence possible?

Worked example Example 10 (Cell 10)

Exam claim: "There exists a simple undirected graph on $5$ vertices with degrees $(3, 3, 3, 3, 1)$ ." True or false — and why, in one line?

Forecast: Try the handshake parity check before drawing anything.

Sum the degrees: $3 + 3 + 3 + 3 + 1 = 13$ . Why sum? Handshaking says $\sum de g = 2 m$ , which must be even.
13 is odd ⇒ it cannot equal $2 m$ for any integer $m$ . Why fatal? $2 m$ is always even; an odd total is impossible. (Corollary: the count of odd-degree vertices — here four 3's plus one 1 = five odd-degree vertices — is odd, but that count must always be even.)
Conclusion: the graph is impossible. Why so quick? No drawing needed — parity kills it instantly.

Verify: $3 + 3 + 3 + 3 + 1 = 13$ , and $13 mod 2 = 1 \neq = 0$ , so no integer $m$ gives $2 m = 13$ . ✓ Also: number of odd-degree vertices $= 5$ , which is odd — violating the even-count corollary. (More in Handshaking lemma and degree sequences.)

Recall Quick self-test (reveal after guessing)

Max edges of simple undirected $K_{n}$ on $n = 6$ ? ::: $(2 6) = 15$ . Same but directed, no self-loops, $n = 6$ ? ::: $6 \cdot 5 = 30$ . A self-loop adds how much to a vertex's degree? ::: $+ 2$ (both endpoints land on it). Why is $(3, 3, 3, 3, 1)$ impossible on 5 vertices? ::: Sum $= 13$ is odd, but $\sum de g = 2 m$ must be even. Weighted non-negative shortest path — which algorithm? ::: Dijkstra (BFS ignores weights).

Back to the parent topic. See also Trees as special graphs for the sparsest connected case ( $m = n - 1$ ).