Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph: Exercises

Throughout, remember the four switches from the parent note: Direction, Weight, Self-loop, Parallel — "DWSP". And the two edge-count facts:

Level 1 — Recognition

Exercise 1.1

Look at the drawing below (left panel). Every connection is a plain line with no arrowhead. Is this graph directed or undirected? Give the one-word reason.

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

Recall Solution 1.1

WHAT we check: are the lines arrows or plain lines? WHY: an arrow encodes a direction — an ordered pair $(u, v)$ that goes one way only; a plain line is an unordered pair ${u, v}$ that goes both ways. The lines have no arrowheads, so each is symmetric. Answer: undirected.

Exercise 1.2

In the right panel of the figure above, one edge starts and ends at the same dot, and one pair of dots ( $P$ and $Q$ ) is joined by two separate lines. Name each of these two features, and decide: is the graph simple or a multigraph?

Recall Solution 1.2

The edge from a vertex to itself is a self-loop, written $(v, v)$ .
The two lines between the same pair $P, Q$ are parallel edges. WHY this forces the classification: a simple graph is defined by forbidding both of those. This graph has both, so it breaks the rule. Answer: it is a multigraph (it fails "simple" on two counts — either one alone is enough).

Exercise 1.3

A road map has numbers written on each road showing kilometres. Which switch is turned "on"? Give the name of the graph property.

Recall Solution 1.3

A number attached to each edge is a weight. WHY: the number distinguishes edges from one another (a long road vs a short road), which is exactly what "weighted" means. Answer: it is a weighted graph. (An unweighted graph would only record whether a road exists, weight $= 1$ for all.)

Level 2 — Application

Exercise 2.1

A simple undirected graph has $n = 8$ vertices. What is the maximum possible number of edges?

Recall Solution 2.1

WHY this formula: every edge is an unordered pair of two distinct vertices (distinct because no self-loops; at most one because simple). Counting max edges = counting how many pairs we can choose. $m_{m a x} = (2 8) = \frac{8 \cdot 7}{2} = \frac{56}{2} = 28.$ Why divide by 2: picking ${u, v}$ and picking ${v, u}$ are the same line, so the $8 \cdot 7 = 56$ ordered picks double-count. Answer: 28.

Exercise 2.2

Same 8 vertices, but now the graph is directed (self-loops still forbidden). Maximum number of arcs (directed edges)?

Recall Solution 2.2

WHY no division now: $(u, v)$ and $(v, u)$ are different arrows — a one-way street each direction is its own arc. So we keep both. $m_{m a x} = n (n - 1) = 8 \cdot 7 = 56.$ Answer: 56 — exactly double the undirected answer, which matches "each undirected edge = two opposite arcs".

Exercise 2.3

An undirected graph has $m = 11$ edges. What is the sum of all vertex degrees?

Recall Solution 2.3

WHY: by the Handshaking Lemma, adding up every vertex's degree counts each edge twice — once at each of its two endpoints. $\sum_{v} de g (v) = 2 m = 2 \cdot 11 = 22.$ Answer: 22.

Level 3 — Analysis

Exercise 3.1

Someone claims: "I built a simple undirected graph on $n = 6$ vertices with $m = 16$ edges." Prove they are wrong.

Recall Solution 3.1

WHAT we do: compare the claim against the maximum allowed. WHY: simple + undirected caps the edges at $(2 n)$ ; exceeding the cap is impossible. $m_{m a x} = (2 6) = \frac{6 \cdot 5}{2} = 15.$ Since $16 > 15$ , no simple undirected graph on 6 vertices can hold 16 edges. The claim is impossible. (To reach 16 you'd need either a parallel edge or a self-loop — i.e. a multigraph.)

Exercise 3.2

An undirected graph is reported to have degrees ${3, 3, 3, 1}$ (four vertices). Is this possible? Use the Handshaking Lemma and its parity corollary.

Recall Solution 3.2

Step 1 — sum test. $\sum de g = 3 + 3 + 3 + 1 = 10$ . For a valid graph this must equal $2 m$ , so $m = 5$ . That's an integer, so the sum test passes. Step 2 — parity corollary. The number of odd-degree vertices must be even (because odd degrees can only pair up to make the total even). Here the odd degrees are $3, 3, 3, 1$ — that's four odd-degree vertices. Four is even, so this test also passes. Conclusion: the degree sequence is not ruled out by these lemmas; such a graph can exist. (See Handshaking lemma and degree sequences for a full realizability check.)

Exercise 3.3

A degree sequence ${4, 2, 1}$ is proposed for an undirected graph. Show it is impossible.

Recall Solution 3.3

Sum: $4 + 2 + 1 = 7$ , which is odd. But $\sum de g = 2 m$ must always be even. $7$ is odd ⇒ contradiction. Impossible. Why the sum must be even: each edge contributes exactly $+ 1$ to two endpoints, i.e. $+ 2$ total, so the grand total is always a multiple of 2. An odd total can never occur.

Level 4 — Synthesis

Exercise 4.1

A flight network has 4 airports. Between every ordered pair of distinct airports there is exactly one directed flight, each with its own fare. Additionally, one airport offers a "sightseeing loop" flight that departs and returns to itself. Classify the graph on all four DWSP switches, and count the total number of edges.

Recall Solution 4.1

Direction: directed — a flight $A \to B$ differs from $B \to A$ .
Weight: weighted — each fare is a number on the arc.
Self-loop: yes — the sightseeing loop is $(v, v)$ .
Parallel: the problem says exactly one flight per ordered pair, so no parallel arcs. But the self-loop breaks "simple" anyway, so this is a multigraph (directed weighted multigraph).
Count: ordered distinct pairs $= n (n - 1) = 4 \cdot 3 = 12$ , plus the one self-loop $= 13$ . Answer: directed, weighted, multigraph; total edges $= 13$ .

Exercise 4.2

You are told an undirected graph is simple and connected on $n = 5$ vertices, and it happens to be a tree. How many edges does it have, and what is the sum of its degrees?

Recall Solution 4.2

Key fact about trees: a tree on $n$ vertices has exactly $m = n - 1$ edges (it's connected with no cycles — the minimum to connect $n$ dots). $m = n - 1 = 5 - 1 = 4.$ Degree sum by Handshaking: $\sum de g = 2 m = 2 \cdot 4 = 8.$ Answer: 4 edges, degree sum 8.

Exercise 4.3

A complete graph $K_{n}$ is the simple undirected graph where every pair of vertices is joined. For $n = 7$ : (a) how many edges? (b) what is the degree of each vertex, and (c) verify Handshaking.

Recall Solution 4.3

(a) Every pair connected ⇒ $m = (2 7) = \frac{7 \cdot 6}{2} = 21$ . (b) Each vertex connects to the other $n - 1 = 6$ vertices, so $de g (v) = 6$ for all 7 vertices. (c) $\sum de g = 7 \times 6 = 42$ and $2 m = 2 \times 21 = 42$ . ✓ They match, so Handshaking holds. Answer: 21 edges; every degree = 6; sum = 42 = 2m.

Level 5 — Mastery

Exercise 5.1

A social platform models 1000 users. Friendships are mutual; follows are one-way. Suppose there are $F$ friendships and $L$ follow-relations. You store the whole thing as a single directed adjacency structure (see Graph representations — adjacency list vs matrix), representing each undirected friendship as two opposite arcs. Write a formula for the total number of stored directed arcs, and evaluate it for $F = 4000$ , $L = 9000$ .

Recall Solution 5.1

WHY two arcs per friendship: an undirected edge ${u, v}$ has no direction; to store it in a directed structure you record both $(u, v)$ and $(v, u)$ so traversal works either way. Each friendship therefore contributes 2 stored arcs; each follow contributes 1. $stored arcs = 2 F + L .$ For $F = 4000, L = 9000$ : $2 (4000) + 9000 = 8000 + 9000 = 17000.$ Answer: $2 F + L = 17000$ arcs.

Exercise 5.2

For a shortest-path task on this network: (a) if you only care about "fewest hops" between two users, which algorithm and why? (b) if each connection has a positive latency (a weight) and you want the least-latency path, which algorithm and why?

Recall Solution 5.2

(a) Fewest hops = treat every edge as cost $1$ = unweighted shortest path. Use BFS — breadth first search. WHY: BFS explores in layers of equal distance, so the first time it reaches a target it has used the fewest edges — and it's faster than a weighted method because it never needs a priority queue. (b) Distinct positive weights ⇒ use Dijkstra's algorithm. WHY: BFS's "count hops" logic is wrong when edges cost different amounts; Dijkstra always expands the currently-cheapest frontier node, which is correct precisely when weights are non-negative. Answer: (a) BFS; (b) Dijkstra.

Exercise 5.3

A project has tasks with "must-finish-before" dependencies (task X must complete before task Y). (a) What kind of graph models this — which two switches are on? (b) Which algorithm produces a valid ordering, and what structural property must the graph have for it to exist at all?

Recall Solution 5.3

(a) A dependency "X before Y" is an ordered relation ⇒ directed. Weights are irrelevant to ordering, so unweighted is fine; self-loops/parallel edges aren't meaningful here (a task can't depend on itself), so it's a simple directed graph. Switch on: Direction. (b) Use Topological sort. WHY it needs direction: topological order only makes sense along arrows. Required property: the graph must be a DAG — a directed acyclic graph (no directed cycle). WHY: a cycle $X \to Y \to X$ would demand X before Y and Y before X — an impossible order, so no topological sort exists. Answer: (a) simple directed (unweighted) graph; (b) topological sort, needs no directed cycle (a DAG).

Recall Self-test summary (cloze)

Max edges of a simple undirected graph on $n$ vertices ::: $(2 n) = \frac{n ( n - 1 )}{2}$ Max edges (arcs) of a simple directed graph on $n$ vertices ::: $n (n - 1)$ Sum of all degrees in an undirected graph ::: $2 m$ (Handshaking Lemma) A degree sequence with an odd sum is ::: impossible — the sum must be even ( $= 2 m$ ) Storing an undirected edge in a directed structure needs ::: two opposite arcs Tool for fewest-hops (unweighted) shortest path ::: BFS Tool for least-cost (non-negative weights) shortest path ::: Dijkstra Tool for ordering tasks along dependency arrows ::: topological sort (requires a DAG)