Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2023/functional-programming-design-and-analysis-of-algorithms/7/d/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2023 Functional programming, design and analysis of algorithms 7 d Solution by 
Codex 0 2026-10-25
Codex 0 2026-10-25Repeatedly remove vertices whose current degree is less than . Implement the deletions with an adjacency list, a queue and a degree counter for each active vertex:The requested subgraph is understood to be nonempty; otherwise an empty output would make the degree requirement vacuous or undefined. For , any nonempty input graph already qualifies.
active[v] = True for every v
count[v] = degree(v)
queue all v with count[v] < k
while the queue is nonempty:
remove v from the queue
if not active[v]: continue
active[v] = False
for each neighbour u of v:
if active[u]:
count[u] -= 1
if count[u] == k-1: queue u
return the subgraph induced by the active vertices,
or report failure if there is no active vertexThe correctness invariant is that every subgraph with minimum degree at least has all its vertices still active. Initially this is immediate. When is deleted, its degree in the whole active induced subgraph is less than . Any candidate subgraph on active vertices has at most that many incident edges at , so cannot contain it. Thus the invariant survives every deletion.
At termination, every active vertex has current degree at least , since every counter initially below the threshold or subsequently crossing it was queued. A nonempty surviving induced subgraph is therefore a valid answer. If none survives, the invariant rules out every possible answer, including ones omitting additional edges. The result is the k-core, with the k-core peeling invariant proving that deletion order cannot destroy a valid solution.
Each vertex is enqueued at most once when initially deficient or first crossing the threshold. Each adjacency list is scanned once when its vertex is deleted. The running time is , and storage is including the input graph.
New to topics? Read the docs here!