Graphs: vocabulary and modelling problems

A graph is a set of vertices (also called nodes) and a set of edges, each edge joining two of the vertices. That one definition describes a metro map, a road network, friendships, links between web pages, the prerequisites of courses and the moves of a puzzle, so one set of algorithms answers questions about all of them: can I get from here to there, how cheaply, in what order, and which parts fall apart if a link breaks. Before any algorithm, though, a problem has to become a graph, and that is a choice: what is a vertex, what is an edge, does an edge have a direction, and does it carry a weight such as minutes or rupees? This lesson fixes the vocabulary on one small graph, checks two counting facts on 2,000 random graphs, and models a metro and a course catalogue, the first one in two different ways that give different answers.

The words, on one small graph

The graph in the picture has eight vertices and six edges. Its edges have no direction, so it is an undirected graph, and an edge between u and v can be written u–v or v–u. The words below follow NIST’s Dictionary of Algorithms and Data Structures.

• Two vertices joined by an edge are adjacent, or neighbours, and the edge is incident to both of its endpoints. A and C are adjacent; A and D are not.
• The degree of a vertex is the number of edges incident to it. C has degree 3, E has degree 1, and H, with no edges at all, is an isolated vertex of degree 0.
• A walk is a list of vertices in which each one is adjacent to the next. A path is a walk that repeats no vertex, and its length is its number of edges: E, D, C, A is a path of length 3. NIST notes that “path” usually means this simple kind, and so does every lesson in this track.
• A cycle is a path that returns to its first vertex. A, B, C, A is a cycle of length 3. In a graph without loops or parallel edges, which the next section defines, a cycle needs at least three edges, because A, B, A would only walk along one edge and back.
• A graph is connected when a path joins every pair of vertices. This one is not: its connected components, the largest connected pieces, are A, B, C, D and E; F and G; and H on its own. Every vertex belongs to exactly one component.

The program below stores the graph as a dictionary of neighbour lists, prints every degree, classifies five vertex sequences by these definitions and finds the components by merging labels along the edges:

# The lesson's small undirected graph: eight vertices, six edges. The program prints every vertex's degree, checks a
# few vertex sequences against the definitions of walk, path and cycle, and finds the connected components by merging
# labels along the edges (no search algorithm needed for eight vertices).

vertices = ["A", "B", "C", "D", "E", "F", "G", "H"]
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("D", "E"), ("F", "G")]

neighbours = {v: [] for v in vertices}
for u, v in edges:
    neighbours[u].append(v)
    neighbours[v].append(u)

print(f"V = {len(vertices)}, E = {len(edges)}")
print("degrees:", ", ".join(f"{v} {len(neighbours[v])}" for v in vertices))
total = sum(len(neighbours[v]) for v in vertices)
print(f"sum of degrees = {total} = 2 x {len(edges)}")
print("odd degree:", " ".join(v for v in vertices if len(neighbours[v]) % 2 == 1))
print("isolated:", " ".join(v for v in vertices if not neighbours[v]))


def adjacent(u, v):
    return v in neighbours[u]


def kind(seq):
    """Classifies a sequence of vertices: not a walk, a walk, a path, or a cycle (in a simple undirected graph)."""
    if any(not adjacent(a, b) for a, b in zip(seq, seq[1:])):
        return "not a walk (a step has no edge)"
    steps = [frozenset(p) for p in zip(seq, seq[1:])]
    if seq[0] == seq[-1]:
        inner = seq[:-1]
        if len(set(inner)) == len(inner) and len(set(steps)) == len(steps) and len(steps) >= 3:
            return f"a cycle of length {len(steps)}"
        return "a closed walk, not a cycle (it repeats a vertex or an edge)"
    if len(set(seq)) == len(seq):
        return f"a path of length {len(steps)}"
    return "a walk, not a path (it repeats a vertex)"


for seq in ["EDCA", "ABCA", "ABA", "EDCBAC", "ACDF"]:
    print(f"{' '.join(seq):12} {kind(list(seq))}")

# Connected components: start with every vertex in a group of its own and merge the two groups at the ends of every
# edge. Repeating until nothing changes leaves one label per component.
label = {v: v for v in vertices}
changed = True
while changed:
    changed = False
    for u, v in edges:
        low = min(label[u], label[v])
        for w in (u, v):
            if label[w] != low:
                old = label[w]
                for x in vertices:
                    if label[x] == old:
                        label[x] = low
                changed = True
groups = {}
for v in vertices:
    groups.setdefault(label[v], []).append(v)
print(f"{len(groups)} components:", " | ".join(" ".join(g) for g in groups.values()))

V = 8, E = 6
degrees: A 2, B 2, C 3, D 2, E 1, F 1, G 1, H 0
sum of degrees = 12 = 2 x 6
odd degree: C E F G
isolated: H
E D C A      a path of length 3
A B C A      a cycle of length 3
A B A        a closed walk, not a cycle (it repeats a vertex or an edge)
E D C B A C  a walk, not a path (it repeats a vertex)
A C D F      not a walk (a step has no edge)
3 components: A B C D E | F G | H

Two sequences fail in instructive ways. E, D, C, B, A, C visits C twice, so it is a walk but not a path. A, C, D, F breaks at the last step, because no edge joins D and F: they lie in different components, so no path can join them. Throughout the module, V stands for the number of vertices and E for the number of edges; here V = 8 and E = 6.

Directions, weights, loops and parallel edges

In a directed graph every edge, often called an arc, runs one way, from its tail to its head, as a one-way street or “course P comes before course C” does. A vertex then has an in-degree, the arcs arriving at it, and an out-degree, the arcs leaving it. A weighted graph attaches a number to every edge: minutes, kilometres, fares or bandwidth. An unweighted graph is the same as one with every weight equal to 1, which is why “fewest edges” and “cheapest route” are different questions with different algorithms.

Two kinds of edge need care. A loop joins a vertex to itself, and parallel edges join the same two vertices more than once, as two bridges between the same pair of towns do. A graph with neither is simple; NIST calls a graph that allows parallel edges a multigraph. Input files contain both more often than problem statements admit, so check before you assume a graph is simple.

Two counting facts that catch mistakes

The degrees add up to twice the number of edges. Every edge has two ends and adds 1 to the degree of each, so the sum of all degrees is 2E. A loop has both its ends at one vertex and adds 2 to it. One consequence is useful in exams: the number of vertices with an odd degree is always even, because an odd number of odd degrees would make the sum odd. In a directed graph every arc adds 1 to one out-degree and 1 to one in-degree, so both sums equal E.

A simple graph has at most V(V − 1)/2 edges, one for every pair of distinct vertices, and a directed graph without loops has at most V(V − 1) arcs. Both facts are easy to prove and easy to check, and a program that counts is an independent check on the proof:

# Two counting facts, checked on random graphs: in an undirected graph the degrees add up to 2E (so the number of
# odd-degree vertices is even), and in a directed graph the in-degrees and the out-degrees both add up to E. Then the
# largest number of edges a simple graph can have, against the edges of a few real-sized sparse graphs.
import random

rng = random.Random(2027)

checked = 0
most_odd = 0
for _ in range(1000):
    n = rng.randint(1, 40)
    p = rng.random()
    edges = [(u, v) for u in range(n) for v in range(u + 1, n) if rng.random() < p]
    degree = [0] * n
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
    odd = sum(1 for d in degree if d % 2 == 1)
    assert sum(degree) == 2 * len(edges)
    assert odd % 2 == 0
    assert len(edges) <= n * (n - 1) // 2
    most_odd = max(most_odd, odd)
    checked += 1
print(f"{checked} random undirected graphs: degree sum = 2E in every one")
print(f"odd-degree vertices: an even number in every one (at most {most_odd} in one graph)")

checked = 0
for _ in range(1000):
    n = rng.randint(1, 40)
    p = rng.random()
    arcs = [(u, v) for u in range(n) for v in range(n) if u != v and rng.random() < p]
    out_degree = [0] * n
    in_degree = [0] * n
    for u, v in arcs:
        out_degree[u] += 1
        in_degree[v] += 1
    assert sum(out_degree) == sum(in_degree) == len(arcs)
    assert len(arcs) <= n * (n - 1)
    checked += 1
print(f"{checked} random directed graphs: sum of in-degrees = sum of out-degrees = E in every one")

# A loop adds 2 to its vertex's degree, so the fact survives loops and parallel edges too.
multi = [(0, 0), (0, 1), (0, 1), (1, 2)]
degree = [0] * 3
for u, v in multi:
    degree[u] += 1
    degree[v] += 1
print(f"with a loop and a parallel edge: degrees {degree}, sum {sum(degree)} = 2 x {len(multi)}")

print()
print(f"{'V':>9} {'most edges, simple':>20} {'directed, no loops':>20}")
for n in (10, 1_000, 100_000):
    print(f"{n:>9,} {n * (n - 1) // 2:>20,} {n * (n - 1):>20,}")
print()
for name, v, e in [("road junctions of a district (assumed)", 100_000, 140_000), ("grid of 1,000 x 1,000 cells", 1_000_000, 2 * 1000 * 999)]:
    share = e / (v * (v - 1) // 2)
    print(f"{name}: V = {v:,}, E = {e:,}, {share:.6%} of the possible edges")

1000 random undirected graphs: degree sum = 2E in every one
odd-degree vertices: an even number in every one (at most 26 in one graph)
1000 random directed graphs: sum of in-degrees = sum of out-degrees = E in every one
with a loop and a parallel edge: degrees [4, 3, 1], sum 8 = 2 x 4

        V   most edges, simple   directed, no loops
       10                   45                   90
    1,000              499,500              999,000
  100,000        4,999,950,000        9,999,900,000

road junctions of a district (assumed): V = 100,000, E = 140,000, 0.002800% of the possible edges
grid of 1,000 x 1,000 cells: V = 1,000,000, E = 1,998,000, 0.000400% of the possible edges

No random graph broke either fact. The last lines show why the maximum matters. With 100,000 vertices a simple graph could have almost 5 × 10⁹ edges, yet real graphs use a tiny share of them: the district road network assumed in the program uses 0.0028 % of its possible edges, and a 1,000 × 1,000 grid 0.0004 %. NIST calls a graph sparse when its edges are far fewer than possible and dense when they are close to the maximum, and most graphs that come from roads, networks and grids are sparse.

Modelling a metro: what is a vertex?

A made-up city has three metro lines. The first model that comes to mind gives every station a vertex and joins neighbouring stations with an edge weighted by the ride in minutes: 9 vertices and 9 edges. It has a blind spot. Changing from the Red line to the Blue line at Central takes 4 minutes of walking, but in this model a change happens inside a vertex, where no edge can charge for it.

The second model gives every platform, one line at one station, a vertex of its own. Ride edges run along each line, and an interchange edge joins the platforms of one station, weighted by the minutes a change takes there. The metro becomes 12 vertices and 12 edges:

The program builds both models and prices three journeys in each:

# A made-up metro with three lines, modelled two ways. Model 1 has one vertex per station and one edge per pair of
# neighbouring stations, weighted by ride minutes. Model 2 has one vertex per platform, a (station, line) pair: ride
# edges run along a line, and interchange edges join the platforms of one station, weighted by the minutes it takes
# to change lines there. The same journeys cost different amounts in the two models.

lines = {
    "Red": [("Harbour", 3), ("Mill Road", 4), ("Central", 3), ("University", 7), ("Airport", None)],
    "Blue": [("Old Fort", 5), ("Central", 2), ("Market", 4), ("Stadium", None)],
    "Green": [("Market", 3), ("University", 5), ("Tech Park", None)],
}
change_minutes = {"Central": 4, "University": 3, "Market": 5}

# Model 1: stations.
station_edges = {}
for stops in lines.values():
    for (a, minutes), (b, _) in zip(stops, stops[1:]):
        station_edges[frozenset((a, b))] = minutes
stations = sorted({s for stops in lines.values() for s, _ in stops})
degree = {s: sum(1 for e in station_edges if s in e) for s in stations}
print(f"Model 1, stations:  V = {len(stations)}, E = {len(station_edges)}")
print("  degrees:", ", ".join(f"{s} {degree[s]}" for s in stations if degree[s] != 2), "(the rest have degree 2)")

# Model 2: platforms.
ride = {}
for line, stops in lines.items():
    for (a, minutes), (b, _) in zip(stops, stops[1:]):
        ride[frozenset(((a, line), (b, line)))] = minutes
platforms = sorted({(s, line) for line, stops in lines.items() for s, _ in stops})
change = {}
for station, minutes in change_minutes.items():
    here = [p for p in platforms if p[0] == station]
    for i, p in enumerate(here):
        for q in here[i + 1:]:
            change[frozenset((p, q))] = minutes
print(f"Model 2, platforms: V = {len(platforms)}, E = {len(ride) + len(change)} ({len(ride)} ride edges, {len(change)} interchange edges)")


def cost_in_platforms(route):
    """Minutes and changes along a list of platforms; every step must be an edge of model 2."""
    minutes = changes = 0
    for p, q in zip(route, route[1:]):
        edge = frozenset((p, q))
        if edge in ride:
            minutes += ride[edge]
        elif edge in change:
            minutes += change[edge]
            changes += 1
        else:
            raise ValueError(f"no edge between {p} and {q}")
    return minutes, changes


def cost_in_stations(route):
    """The same journey in model 1: the platforms collapse to stations and the interchange steps disappear."""
    names = [p[0] for p in route]
    names = [s for i, s in enumerate(names) if i == 0 or s != names[i - 1]]
    return sum(station_edges[frozenset(pair)] for pair in zip(names, names[1:]))


journeys = {
    "Harbour to Stadium, change at Central": [("Harbour", "Red"), ("Mill Road", "Red"), ("Central", "Red"), ("Central", "Blue"), ("Market", "Blue"), ("Stadium", "Blue")],
    "Harbour to Stadium, via University and Market": [("Harbour", "Red"), ("Mill Road", "Red"), ("Central", "Red"), ("University", "Red"), ("University", "Green"), ("Market", "Green"), ("Market", "Blue"), ("Stadium", "Blue")],
    "Mill Road to Tech Park, change at University": [("Mill Road", "Red"), ("Central", "Red"), ("University", "Red"), ("University", "Green"), ("Tech Park", "Green")],
}
print()
for name, route in journeys.items():
    minutes, changes = cost_in_platforms(route)
    print(f"{name}:")
    print(f"  platforms: {minutes} min with {changes} change{'s' if changes != 1 else ''}; stations: {cost_in_stations(route)} min")

Model 1, stations:  V = 9, E = 9
  degrees: Airport 1, Central 4, Harbour 1, Market 3, Old Fort 1, Stadium 1, Tech Park 1, University 4 (the rest have degree 2)
Model 2, platforms: V = 12, E = 12 (9 ride edges, 3 interchange edges)

Harbour to Stadium, change at Central:
  platforms: 17 min with 1 change; stations: 13 min
Harbour to Stadium, via University and Market:
  platforms: 25 min with 2 changes; stations: 17 min
Mill Road to Tech Park, change at University:
  platforms: 15 min with 1 change; stations: 12 min

The station model says the trip from Harbour to Stadium through Central takes 13 minutes; the platform model, which charges the change, says 17. The route through University and Market looks like 17 minutes in the station model and is really 25, with two changes. Even the number of changes is a count of interchange edges, which only the second model has. Neither model is wrong; they answer different questions. The rule this example teaches is general: if a cost or a rule belongs to the step between two things, make that step an edge, and split a vertex when different ways of being “at” it behave differently.

Course prerequisites: a directed graph without cycles

A course catalogue lists pairs such as “Data Structures needs Introduction to Programming”. Each pair becomes an arc from the prerequisite to the course, so the graph is directed and unweighted. In-degrees count prerequisites, and the courses with in-degree 0 are the ones a student can take first:

# A made-up course catalogue as a directed graph: an edge P -> C means "P must be passed before C". In-degrees count
# a course's prerequisites, out-degrees the courses that need it. Then one data-entry mistake adds an edge that closes
# a directed cycle, and four courses can never be taken.

courses = {
    "IP": "Introduction to Programming",
    "DM": "Discrete Mathematics",
    "CO": "Computer Organisation",
    "DS": "Data Structures",
    "TC": "Theory of Computation",
    "AL": "Algorithms",
    "DB": "Databases",
    "OS": "Operating Systems",
    "CD": "Compiler Design",
}
prerequisites = [("IP", "DS"), ("DM", "DS"), ("DM", "TC"), ("DS", "AL"), ("DS", "DB"), ("CO", "OS"), ("DS", "OS"), ("AL", "CD"), ("TC", "CD")]

out_edges = {c: [] for c in courses}
in_degree = {c: 0 for c in courses}
for p, c in prerequisites:
    out_edges[p].append(c)
    in_degree[c] += 1

print(f"V = {len(courses)}, E = {len(prerequisites)}")
print(f"{'course':6} {'in':>3} {'out':>4}  needed by")
for c in courses:
    print(f"{c:6} {in_degree[c]:>3} {len(out_edges[c]):>4}  {' '.join(out_edges[c]) or '-'}")
print(f"sum of in-degrees = {sum(in_degree.values())}, sum of out-degrees = {sum(len(v) for v in out_edges.values())}")
print("no prerequisites (in-degree 0):", ", ".join(courses[c] for c in courses if in_degree[c] == 0))
print("needed by nothing (out-degree 0):", ", ".join(courses[c] for c in courses if not out_edges[c]))


def is_directed_cycle(seq):
    return seq[0] == seq[-1] and len(set(seq[:-1])) == len(seq) - 1 and all(b in out_edges[a] for a, b in zip(seq, seq[1:]))


print()
print("a typing mistake adds CD -> IP")
out_edges["CD"].append("IP")
cycle = ["IP", "DS", "AL", "CD", "IP"]
print(" -> ".join(cycle), "is a directed cycle:", is_directed_cycle(cycle))
print("each course on it waits for the one before, so none of the four can ever be the first one taken")

V = 9, E = 9
course  in  out  needed by
IP       0    1  DS
DM       0    2  DS TC
CO       0    1  OS
DS       2    3  AL DB OS
TC       1    1  CD
AL       1    1  CD
DB       1    0  -
OS       2    0  -
CD       2    0  -
sum of in-degrees = 9, sum of out-degrees = 9
no prerequisites (in-degree 0): Introduction to Programming, Discrete Mathematics, Computer Organisation
needed by nothing (out-degree 0): Databases, Operating Systems, Compiler Design

a typing mistake adds CD -> IP
IP -> DS -> AL -> CD -> IP is a directed cycle: True
each course on it waits for the one before, so none of the four can ever be the first one taken

A sensible catalogue has no directed cycle: a graph like this is a directed acyclic graph, or DAG. One wrong pair is enough to break that. After the mistake, Introduction to Programming needs Compiler Design, which needs Algorithms, which needs Data Structures, which needs Introduction to Programming, and none of the four can ever be taken first. Finding such a cycle automatically, and producing an order in which every course comes after its prerequisites, are the subjects of the lessons on cycle detection and topological sorting later in this module.

Families of graphs to recognise

Some shapes come up so often that recognising them changes which algorithm you reach for.

A tree is the most constrained of these. A connected graph with V − 1 edges is always a tree, and adding any edge to a tree creates exactly one cycle. Bipartite graphs are precisely the graphs without an odd cycle, a fact that the lesson on bipartite graphs turns into an algorithm.

Some graphs are never stored at all. In a grid the neighbours of a cell are computed from its row and column, and in a puzzle the next states are computed from the current one. Such implicit graphs can be huge: the 1,000 × 1,000 grid above has a million vertices and 1,998,000 edges, and a search only ever generates the part it visits.

V and E in every running time

Because graphs vary so much in density, running times on graphs name both V and E. The searches of this module visit every vertex and every edge a constant number of times, which costs O(V + E). Code that looks at every pair of vertices, for example by scanning an adjacency matrix, costs O(V²) however few edges there are. For the district road network, V + E is 240,000 while V² is 10¹⁰, about 40,000 times more work, and a table of 10¹⁰ cells would not even fit in memory. Writing O(n) for a graph algorithm hides which of the two you meant, so state both.

Exercise: degrees and simplicity from an edge list

Input to graph problems usually arrives as an edge list, one pair per line. Turning it into degrees and checking whether it is simple is the first thing many programs do, and the last test below is large enough that comparing every pair of edges takes too long.

def degree_report(n, edges):
    """Undirected graph on vertices 0..n-1. Returns (degrees, number of edges, simple?)."""
    raise NotImplementedError("write degree_report")

import random

from degrees import degree_report


def slow_report(n, edges):
    degrees = [0] * n
    for u, v in edges:
        degrees[u] += 1
        degrees[v] += 1
    simple = all(u != v for u, v in edges) and all(
        {edges[i][0], edges[i][1]} != {edges[j][0], edges[j][1]} for i in range(len(edges)) for j in range(i + 1, len(edges))
    )
    return degrees, len(edges), simple


def test_lesson_graph():
    """the lesson's graph: A to H are 0 to 7, six edges, H isolated"""
    edges = [(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (5, 6)]
    assert degree_report(8, edges) == ([2, 2, 3, 2, 1, 1, 1, 0], 6, True)


def test_no_edges():
    """three vertices and no edges: every degree is 0 and the graph is simple"""
    assert degree_report(3, []) == ([0, 0, 0], 0, True)


def test_loop_counts_twice():
    """a loop (0, 0) adds 2 to vertex 0 and makes the graph not simple"""
    assert degree_report(2, [(0, 0), (0, 1)]) == ([3, 1], 2, False)


def test_parallel_edges_both_ways():
    """(1, 2) and (2, 1) join the same pair: parallel edges"""
    assert degree_report(3, [(1, 2), (2, 1)]) == ([0, 2, 2], 2, False)


def test_random_graphs():
    """on 300 small random edge lists, matches a slow check of every pair of edges"""
    rng = random.Random(7)
    for _ in range(300):
        n = rng.randint(1, 8)
        edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 10))]
        assert degree_report(n, edges) == slow_report(n, edges), (n, edges)


def test_large_star():
    """a star of 100,000 vertices, then the same star with one edge repeated at the end"""
    n = 100_000
    edges = [(0, v) for v in range(1, n)]
    degrees, m, simple = degree_report(n, edges)
    assert (degrees[0], degrees[1], degrees[-1], m, simple) == (n - 1, 1, 1, n - 1, True)
    degrees, m, simple = degree_report(n, edges + [(7, 0)])
    assert (degrees[0], degrees[7], m, simple) == (n, 2, n, False)

/** Undirected graph on vertices 0..n-1. Returns [degrees, number of edges, simple?]. */
export function degreeReport(n, edges) {
  throw new Error('write degreeReport');
}

import { test, assert } from 'mysmartcopilot:test';
import { degreeReport } from './degrees.mjs';

function slowReport(n, edges) {
  const degrees = new Array(n).fill(0);
  for (const [u, v] of edges) {
    degrees[u] += 1;
    degrees[v] += 1;
  }
  let simple = edges.every(([u, v]) => u !== v);
  for (let i = 0; i < edges.length; i++) {
    for (let j = i + 1; j < edges.length; j++) {
      const [a, b] = edges[i];
      const [c, d] = edges[j];
      if ((a === c && b === d) || (a === d && b === c)) simple = false;
    }
  }
  return [degrees, edges.length, simple];
}

test("the lesson's graph: A to H are 0 to 7, six edges, H isolated", () => {
  const edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4], [5, 6]];
  assert.deepEqual(degreeReport(8, edges), [[2, 2, 3, 2, 1, 1, 1, 0], 6, true]);
});

test('three vertices and no edges: every degree is 0 and the graph is simple', () => {
  assert.deepEqual(degreeReport(3, []), [[0, 0, 0], 0, true]);
});

test('a loop (0, 0) adds 2 to vertex 0 and makes the graph not simple', () => {
  assert.deepEqual(degreeReport(2, [[0, 0], [0, 1]]), [[3, 1], 2, false]);
});

test('(1, 2) and (2, 1) join the same pair: parallel edges', () => {
  assert.deepEqual(degreeReport(3, [[1, 2], [2, 1]]), [[0, 2, 2], 2, false]);
});

test('on 300 small random edge lists, matches a slow check of every pair of edges', () => {
  let seed = 7;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  for (let k = 0; k < 300; k++) {
    const n = 1 + Math.floor(random() * 8);
    const m = Math.floor(random() * 11);
    const edges = Array.from({ length: m }, () => [Math.floor(random() * n), Math.floor(random() * n)]);
    assert.deepEqual(degreeReport(n, edges), slowReport(n, edges), JSON.stringify([n, edges]));
  }
});

test('a star of 100,000 vertices, then the same star with one edge repeated at the end', () => {
  const n = 100000;
  const edges = Array.from({ length: n - 1 }, (_, i) => [0, i + 1]);
  let [degrees, m, simple] = degreeReport(n, edges);
  assert.deepEqual([degrees[0], degrees[1], degrees[n - 1], m, simple], [n - 1, 1, 1, n - 1, true]);
  [degrees, m, simple] = degreeReport(n, [...edges, [7, 0]]);
  assert.deepEqual([degrees[0], degrees[7], m, simple], [n, 2, n, false]);
});

Interview questions

Fresher · A simple undirected graph has 9 vertices, and every vertex has degree 3. How many edges does it have?

No such graph exists. The degrees would add up to 9 × 3 = 27, but the sum of the degrees of any graph is twice its number of edges, so it must be even. Put another way, the graph would have nine vertices of odd degree, and the number of odd-degree vertices is always even. The question is a check that you test whether the input is possible before computing with it. With 8 vertices of degree 3 the answer is 12 edges, and such a graph exists: the corners and edges of a cube. With 10 vertices of degree 3 it is 15 edges. In a simple graph a vertex’s degree is also at most V − 1, so degree 9 among 9 vertices would be impossible for that reason alone.

Key takeaways

• A graph is vertices and edges; edges may be undirected or directed, unweighted or weighted, and input may contain loops and parallel edges, so check whether a graph is simple.
• A path repeats no vertex, a cycle is a path that returns to its start, and the connected components split the vertices into the largest connected pieces.
• The degrees add up to 2E, so an odd number of odd degrees is impossible; a simple graph has at most V(V − 1)/2 edges, and most real graphs are far sparser than that.
• Modelling is a choice: when a cost belongs to a step, make the step an edge, and split a vertex, as the metro’s platforms split its stations, when different ways of being at it behave differently.
• Trees, DAGs, bipartite, complete and grid graphs each have a defining property, and running times on graphs name both V and E: O(V + E) for a search against O(V²) for scanning every pair.