Choose one deeper question.

Answer & reasoning

For a simple undirected graph, degree is the number of incident edges. A path is a vertex sequence whose consecutive vertices are joined by edges; a simple path has no repeated vertices. A graph is connected when every pair of vertices is joined by a path.

Answer & reasoning

n(n − 1)/2, one per unordered pair; n(n − 1), one per ordered pair.

Answer & reasoning

2m, because every edge contributes 1 to the degree of each of its two endpoints.

Answer & reasoning

1, 2, 3, 4, 5. Vertex 5 is at distance 3 (for example 1–2–4–5).

Answer & reasoning

1, 2, 4, 3, 5: from 1 go to 2, from 2 to 4, from 4 to 3 (its smallest undiscovered neighbour), 3 has nothing new, back to 4, then 5.

Answer & reasoning

three: {1, 2, 3}, {4, 5} and {6}. An isolated vertex is a component on its own.

Answer & reasoning

n − 1; the new edge closes exactly one cycle, since the tree already contains one path between its endpoints.

Answer & reasoning

BFS, because it discovers vertices in order of increasing distance from the start. DFS dives deep first and may reach a vertex by a long roundabout route before a short one.

Answer & reasoning

the triangle is not: three mutually adjacent vertices cannot be two-coloured. The square is: colour opposite corners alike.

Answer & reasoning

only A, B, C. A must come before B and C, and B before C.

Answer & reasoning

3, using the edges of weight 1 and 2. A spanning tree of three vertices has exactly two edges.

Answer & reasoning

no negative weights. The course assumes all weights are positive.

Answer & reasoning

Simple array-based Prim: O(n²). Kruskal: O(m log m) for sorting the edges, with near-linear union-find work. Dijkstra with adjacency lists and a binary heap: O((n + m) log n), often written O(m log n) when all n vertices are reachable and m ≥ n−1. Floyd–Warshall: Θ(n³).

Answer & reasoning

A DAG is a directed graph with no directed cycle. Every nonempty finite DAG has a vertex with in-degree zero: otherwise repeatedly follow an incoming edge backwards; finiteness forces a repeated vertex and hence a directed cycle.

Answer & reasoning

A–C (1), then C–B (2), then B–D (5) (cheaper than C–D at 8 and C–E at 10), then D–E (3). Total 1 + 2 + 5 + 3 = 11.

Answer & reasoning

A–C (1) accepted; B–C (2) accepted; D–E (3) accepted; A–B (4) rejected, it would close the cycle A–C–B; B–D (5) accepted, joining {A, B, C} to {D, E}; four edges are now in, so C–D (8) and C–E (10) are not needed. Total 11, the same tree as Prim’s.

Answer & reasoning

Distances from A are A = 0, C = 1, B = 3, D = 8, E = 11. A–C–B costs 3, improving the direct edge of weight 4. A–C–B–D costs 8. E has two equally short routes: A–C–E and A–C–B–D–E, both 11. One shortest-path tree uses A–C, C–B, B–D, C–E; choosing D–E instead is also valid. Parent choices depend on the tie rule; strict-improvement-only updates keep C as E’s parent.

Answer & reasoning

no. Triangle A–B (2), B–C (2), A–C (3): the MST is A–B, B–C with weight 4. The shortest path from A to C in the graph is the direct edge of weight 3, but in the tree the path A–B–C has weight 4.

Answer & reasoning

A→B (2), A→C (5), C→B (−4). Dijkstra settles B at distance 2 as the nearest unknown vertex and never revisits it, but A→C→B costs 5 − 4 = 1. The greedy step assumes that adding edges can never make a path shorter, which negative weights violate.

Answer & reasoning

1 → 2 → 4 → 5; 5 finishes, 4 finishes, 2 finishes; back at 1, go to 3; its neighbours 4 and 5 are done, so 3 finishes; then 1. Finishing order 5, 4, 2, 3, 1; reversed: 1, 3, 2, 4, 5. Check: every edge points left to right.

Answer & reasoning

in-degrees are 1:0, 2:1, 3:1, 4:2, 5:2. Output 1, reducing 2 and 3 to zero. Output 2 (4 drops to 1), output 3 (4 drops to 0, 5 to 1), output 4 (5 drops to 0), output 5. Order 1, 2, 3, 4, 5, also valid; a DAG may have several topological sorts.

Answer & reasoning

run DFS and watch for a back edge (an edge to a vertex that is discovered but not yet finished); or run the in-degree removal method and check whether fewer than n vertices come out.

Answer & reasoning

Initialise paths[s] = 1 and the other counts to zero. Process a topological ordering; for each edge v→w, add paths[v] to paths[w]. Dependencies are complete when a vertex is processed. This uses O(n + m) arithmetic operations. Path counts can be exponentially large, so arbitrary-precision bit costs are not necessarily constant per addition.

Answer & reasoning

in the path, 2 and 3 (removing either disconnects it); the endpoints are not. In the cycle, none: removing any single vertex leaves a path, still connected.

Answer & reasoning

For a connected unweighted graph, run BFS from every vertex and take the largest distance: O(n(n + m)). For a disconnected graph, state a convention: the diameter over all vertex pairs is infinite if unreachable pairs have infinite distance, or report separate component diameters.

Answer & reasoning

start with D[1,2] = 4, D[1,3] = 11, D[2,3] = 2, zeros on the diagonal, ∞ elsewhere. k = 1: no entry improves (nothing leads into 1). k = 2: D[1,3] = min(11, D[1,2] + D[2,3]) = min(11, 6) = 6. k = 3: no change (nothing leaves 3). Final shortest distance from 1 to 3 is 6.

Answer & reasoning

colour 1 white; its neighbours 2, 4 and 3 become black; then the edge 2–3 joins two black vertices. Not bipartite: 1–2–3 is a triangle, an odd cycle.

Answer & reasoning

{1,2} {3} {4} {5} {6}; then {1,2} {3,4} {5} {6}; then {1,2,3,4} {5} {6}; then {1,2,3,4} {5,6}; finally (1, 4): find(1) = find(4) already, so nothing merges; Kruskal would reject this edge as cycle-forming.

Answer & reasoning

set in[v] = 0 for all v, then walk every adjacency list once and, for each edge x→y encountered, add 1 to in[y]. Each edge is seen exactly once.

Answer & reasoning

Step by step

1. Let x be discovered before y, with edge {x,y}.
2. If y is still undiscovered when this edge is examined, DFS descends toward y before finishing x.
3. Thus the two endpoints lie on an ancestor–descendant chain. A non-tree edge is viewed upward as a back edge; its reverse is not a second edge.

For an undirected edge {x,y}, suppose x is discovered first. DFS cannot finish x while y remains undiscovered, because it examines every neighbour before finishing; that edge would discover y. Thus y is discovered while x is active and lies in its DFS subtree. Every undirected edge therefore connects ancestor and descendant. If it is not the discovery edge, classify it as a back edge when viewed from descendant toward ancestor. The reverse view is the same undirected edge, not a separate forward edge.

Answer & reasoning

Step by step

1. The start is layer 0. Its newly discovered neighbours form layer 1.
2. All layer-d vertices leave the queue before any layer-(d+1) vertex is processed.
3. A vertex first reached from layer d cannot have a shorter undiscovered route: that route’s earlier layer would already have found it. Its parent chain therefore has shortest length d+1.

claim: BFS discovers all vertices at distance d before any vertex at distance d + 1, and a vertex at distance d + 1 is always discovered from a vertex at distance d. Induction on d: the root is the only vertex at distance 0. Assume the claim up to d. Every vertex at distance d + 1 has a neighbour at distance d; the queue holds all distance-d vertices before any at distance d + 1, so when those are processed each distance-(d + 1) vertex is discovered from a distance-d parent and put in the queue before any distance-(d + 2) vertex. Hence parent pointers step down by exactly one distance unit, and the tree path from the root to v has exactly dist(v) edges.

Answer & reasoning

Step by step

1. If an edge always changes colour, a cycle returns to its starting colour only after an even number of edges.
2. Conversely, colour BFS levels alternately in each component.
3. An edge within the same level would create an odd cycle: take the two tree branches from their last common ancestor, then that edge. With no odd cycle, every edge joins opposite colours.

if it is bipartite, colours alternate along any cycle, so returning to the start colour needs an even number of steps. Conversely, if there is no odd cycle, BFS from a vertex in each component and colour vertices by the parity of their distance. Any edge joins vertices whose distances differ by at most 1; if an edge joined two vertices at the same distance d, the two tree paths to them plus that edge would form a closed walk of length 2d + 1, which contains an odd cycle. So every edge joins different parities: a valid two-colouring.

Answer & reasoning

Step by step

1. Choose the lightest edge e that appears in exactly one proposed MST, say T₁.
2. Adding e to T₂ creates a cycle. That cycle contains an edge f outside T₁; otherwise T₁ would contain a cycle too.
3. Because weights are distinct and e was lightest among differing edges, f is heavier. Replacing f by e makes T₂ cheaper, a contradiction.

suppose T₁ ≠ T₂ are both minimum. Let e be the lightest edge that is in one of them but not both, say e ∈ T₁ \ T₂. Adding e to T₂ closes a cycle, which must contain an edge f not in T₁ (otherwise T₁ would contain a cycle). f is in T₂ but not T₁, and since e was the lightest such edge and weights are distinct, w(f) > w(e). Then T₂ − f + e is a spanning tree lighter than T₂, contradicting minimality.

Answer & reasoning

Step by step

1. Call that edge weight B. Suppose another spanning tree uses only edges lighter than B.
2. That other tree must cross the cut between the two parts using some edge f of weight below B.
3. Substitute f for the removed edge: the original MST would become cheaper. The contradiction proves no spanning tree has a smaller bottleneck.

suppose some spanning tree S has maximum edge weight w less than the MST’s maximum edge weight, and let e be an MST edge with w(e) > w. Removing e splits the MST into two parts; S is connected, so it contains an edge f crossing between those parts with w(f) ≤ w < w(e). Then MST − e + f is a lighter spanning tree, contradicting minimality. (Kruskal’s order makes this vivid: it never adds an edge heavier than necessary to connect.)

Answer & reasoning

Step by step

1. Set the source distance to 0 and the others to infinity.
2. At each reachable vertex u, try dist[u]+w(u,v) for every outgoing edge and keep improvements.
3. All possible predecessors are already processed, so a negative edge causes no late return. Visit each vertex and edge once: O(n+m) word operations.

compute a topological order (O(n + m)). Set dist[s] = 0 and all others to ∞. Process vertices in topological order, and for each edge v→w set dist[w] = min(dist[w], dist[v] + w(v, w)). Every path to w passes through vertices earlier in the order, so dist[v] is final before it is used. Negative weights are harmless because a DAG has no cycles to loop around.

Answer & reasoning

Step by step

1. Each non-tree edge e creates exactly one cycle with T.
2. Remove a heaviest edge on that cycle to get the cheapest tree obtainable with this e. Record its weight, even if tied with T.
3. Try every non-tree edge and keep the best. A standard tree-exchange argument guarantees a best alternative among these swaps. Finding each tree path by a scan costs O(n), for O(nm) overall.

Assume a connected graph and seek the lightest spanning tree different from the given MST T; it may have equal weight. There exists a best alternative obtainable by one swap. For each non-tree edge e, find the unique tree path between its endpoints, remove a maximum-weight edge f on that path, and evaluate T − f + e. Keep the cheapest alternative. Scanning each path takes O(n), giving O(nm). If there is no non-tree edge, no alternative spanning tree exists. “Strictly heavier second-best” is a different problem when weights tie.

Answer & reasoning

Step by step

1. For one vertex there are zero edges, matching n−1.
2. Remove a leaf and its single incident edge. Remaining vertices still form a tree.
3. By induction that smaller tree has n−2 edges. Restoring one edge gives n−1.

base case n = 1: no edges. For n ≥ 2, a tree has a leaf (a vertex of degree 1): start anywhere and keep walking along unused edges; you cannot revisit a vertex because there are no cycles, so the walk ends at a vertex with no other edge, a leaf. Remove that leaf and its edge; the rest is still connected and acyclic, so it is a tree with n − 1 vertices and, by the hypothesis, n − 2 edges. Adding the leaf’s edge back gives n − 1.

Answer & reasoning

is_a_solution (are the first k choices a complete answer?), construct_candidates (which values may go in position k, given positions 1 to k − 1?), process_solution (print, count or use a finished solution).

Answer & reasoning

2⁴ = 16 subsets and 4! = 24 permutations.

Answer & reasoning

refusing to extend a partial solution that can no longer lead to a complete one, so whole branches of the search tree are never entered. It lives in construct_candidates, which simply does not offer doomed candidates.

Answer & reasoning

no two queens can share a row or a column, so the solution is a permutation: row i’s queen sits in column aᵢ, all columns different. That leaves n! arrangements, and diagonal checks prune most of those too.

Answer & reasoning

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55; F(10) = 55.

Answer & reasoning

The recurrence recomputes the same subproblems many times. Its call count satisfies C(n) = 1 + C(n−1) + C(n−2), so C(n) = 2F(n+1) − 1 = Θ(φⁿ), where φ ≈ 1.618. Saying “about 1.6ⁿ” is informal; 1.6 is not the exact asymptotic base.

Answer & reasoning

memoisation keeps the recursive structure but caches each result the first time it is computed; bottom-up DP replaces recursion with loops that fill the table from the smallest cases upward.

Answer & reasoning

C(5, 2) = C(4, 1) + C(4, 2) = 4 + 6 = 10.

Answer & reasoning

1 (substitute a → u); 1 (insert s); 3 (k → s, e → i, insert g).

Answer & reasoning

3; for example ABD (or ACD).

Answer & reasoning

3; for example 5, 6, 7 or 1, 2, 7.

Answer & reasoning

The four nonempty cuts after positions 1, 2, 3 and 4 give maximum sums 14, 12, 9 and 10. The minimum is 9, achieved by {1, 2, 3} | {4, 5}. A cut before the first element would create an empty range and is not included.

Answer & reasoning

Once the state contains all information that can affect future choices, an optimal solution can use optimal subproblem solutions. In edit distance the state is a pair of prefix lengths; for shortest paths, a shortest route has shortest subroutes. This principle alone does not justify Dijkstra’s settled-once order, which also needs nonnegative edges.

Answer & reasoning

9 (for example 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321). Prune by never offering i as a candidate for position i, so no wasted branches are entered.

Answer & reasoning

greedy takes 4, then 1, then 1: three coins. DP with best[a] = 1 + min(best[a − 1], best[a − 3], best[a − 4]) gives best[6] = 2 (3 + 3). Greedy fails; the DP considers every last coin.

Answer & reasoning

rows for the prefixes of “sun” against columns for the prefixes of “snow”: row 0: 0 1 2 3 4; row s: 1 0 1 2 3; row u: 2 1 1 2 3; row n: 3 2 1 2 3. Distance 3: keep s, substitute u → n, substitute n → o, insert w.

Answer & reasoning

GTAB, of length 4. (The table’s bottom-right entry is 4; tracing back the matches gives G, T, A, B.)

Answer & reasoning

9, taking the items of weight 3 and 4. Let V[i, w] be the best value using the first i items within weight w: V[i, w] = max(V[i − 1, w], V[i − 1, w − wᵢ] + vᵢ) when wᵢ ≤ w, else V[i − 1, w]; the table has (n + 1)(W + 1) cells.

Answer & reasoning

4, at 40, 70, 120 and 150. From 0 the only reachable station is 40; from 40, only 70 (120 is 80 miles away); from 70, only 120; from 120, only 150; from 150 the destination is 40 miles away. The recurrence G[i] = 1 + min over reachable j of G[j] gives the same count; here the “drive as far as you can” greedy also works because fill-ups are all equal in cost.

Answer & reasoning

break at 5 first (cost 10), leaving a piece of length 5 that is then broken at 2 (cost 5): total 15. Breaking at 2 first costs 10 + 8 = 18. The DP C[i, j] = (j − i) + min over breaks k of C[i, k] + C[k, j] computes 15.

Answer & reasoning

rows 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1; 1 6 15 20 15 6 1. So C(6, 3) = 20.

Answer & reasoning

none for n = 2 or 3 (every placement leaves two queens attacking). For n = 4 there are 2 solutions, mirror images: columns (2, 4, 1, 3) and (3, 1, 4, 2).

Answer & reasoning

ways(n) = ways(n − 1) + ways(n − 2), with ways(1) = 1, ways(2) = 2 (the last move was a 1-step or a 2-step). ways(3) = 3, ways(4) = 5, ways(5) = 8: the Fibonacci numbers.

Answer & reasoning

let best[i] be the best sum of a stretch ending at position i: best[i] = max(a[i], best[i − 1] + a[i]). The values are −2, 1, −2, 4, 3, 5, 6, 1, 5, and the answer is the maximum, 6, from the stretch 4, −1, 2, 1.

Answer & reasoning

The length is 5; “carac” is a palindromic subsequence of “character”. An LCS computation against the reverse gives the correct optimal length, but an arbitrary reconstructed LCS need not itself be a palindrome. To recover a palindrome reliably, use interval DP: L[i,j] = 2 + L[i+1,j−1] when the endpoint characters match, otherwise max(L[i+1,j], L[i,j−1]); base cases are 0 for an empty interval and 1 for a single character.

Answer & reasoning

cell (i, j) needs (i − 1, j − 1), (i, j − 1) and (i − 1, j), all of which lie in an earlier row or earlier in the same row. Column by column, top to bottom, works for the same reason; so does going along anti-diagonals.

Answer & reasoning

Step by step

1. Set C(0)=C(1)=1. For n≥2, C(n)=1+C(n−1)+C(n−2).
2. Assuming C(n−1)≥F(n−1) and C(n−2)≥F(n−2), their sum already reaches F(n).
3. The extra current call can only increase the count. Both base cases hold, so induction proves C(n)≥F(n), an exponential lower bound.

let C(n) be the number of calls. C(0) = C(1) = 1, and C(n) = 1 + C(n − 1) + C(n − 2) for n ≥ 2. Induction: C(0) ≥ F(0) and C(1) ≥ F(1); if C(n − 1) ≥ F(n − 1) and C(n − 2) ≥ F(n − 2), then C(n) ≥ F(n − 1) + F(n − 2) = F(n). Since F(n) ≈ 1.618ⁿ / √5, the number of calls is exponential.

Answer & reasoning

Step by step

1. Set long[s]=0, all other values to −∞, and process topological order.
2. For each reachable u, update long[v]=max(long[v],long[u]+w(u,v)).
3. With cycles, a simple path must remember used vertices to avoid repetition. A state containing only the current vertex loses that information.

Initialise long[s] = 0 and every other value to −∞. In topological order, for every edge u→v from a reachable u, update long[v] = max(long[v], long[u] + w(u,v)). This takes O(n + m). In a cyclic graph, the longest simple path depends on which vertices have already been used, so the vertex alone is not a sufficient state. The longest-simple-path decision problem is NP-complete; the optimisation problem is NP-hard.

Answer & reasoning

Step by step

1. Suppose s ends in …ab and t ends in …ba at the prefixes being compared.
2. Besides insertion, deletion and substitution, allow the cost for the prefixes two characters shorter, plus 1.
3. This restricted recurrence gives optimal string alignment distance. It does not allow every combination of overlapping edits that unrestricted Damerau–Levenshtein permits.

For i,j ≥ 2, if s[i] = t[j−1] and s[i−1] = t[j], also consider D[i−2,j−2] + 1. Keep the usual insertion, deletion and substitution cases. This computes the restricted optimal-string-alignment distance, where a substring is not edited repeatedly. Fully unrestricted Damerau–Levenshtein distance requires more state; the extra local case alone does not compute it.

Answer & reasoning

Step by step

1. A cap of 14 works: [3,1,4,1] | [5,9] | [2,6], with sums 9,14,8.
2. With cap 13, maximal packing gives [3,1,4,1] | [5] | [9,2] | [6]: four ranges.
3. For positive entries, ending any earlier range sooner cannot improve how far the same number of ranges reaches. So three ranges cannot fit under 13, proving optimum 14.

The optimum is 14: 3,1,4,1 | 5,9 | 2,6 has sums 9,14,8. To rule out 13, greedily pack each range as far as possible under that cap: [3,1,4,1], [5], [9,2], [6]. Four ranges are needed. For positive entries, cutting an earlier range sooner cannot let any later range end farther right than this maximal packing, so three ranges cannot achieve cap 13. Hence 14 is optimal.

Answer & reasoning

Step by step

1. Try floors 4,7,9,10 while the first egg survives: the jumps are 4,3,2,1.
2. If it breaks, search the skipped floors with the remaining egg. The worst branch still totals only four drops.
3. With three drops, two eggs cover at most 3+2+1=6 floors. Four is therefore both sufficient and necessary for ten floors.

4. Drop from floor 4: if it breaks, test 1, 2, 3 one at a time with the last egg (up to 3 more drops). If not, drop from 7: if it breaks, test 5, 6; if not, drop from 9: if it breaks, test 8; if not, drop from 10. Each branch uses at most 4 drops. Three cannot suffice: with 3 drops and 2 eggs the most floors you can settle is 3 + 2 + 1 = 6. The recurrence E(k, n) = 1 + min over x of max(E(k − 1, x − 1), E(k, n − x)) gives E(2, 10) = 4.

Answer & reasoning

Step by step

1. A set of n cities has 2ⁿ subsets. The current city adds at most n possibilities.
2. Each state considers at most n previous cities or next transitions, depending on the formulation.
3. Multiplying gives O(n²2ⁿ). Reusing states beats enumerating n! tours, but there are still exponentially many states.

the state must record which cities have already been visited, because the best way to finish depends on it; that state is an arbitrary subset of the n cities, and there are 2ⁿ subsets. With n choices of current city the table has n · 2ⁿ entries, each costing O(n): O(n² 2ⁿ), much better than n! but still exponential. In string problems the corresponding state is a prefix, and there are only n of those.

Answer & reasoning

Step by step

1. S₁ covers four elements, so greedy takes it first.
2. Element 5 then requires S₂, and element 6 requires S₃: three sets total.
3. But S₂∪S₃ already equals the whole universe. Two sets suffice, while no single listed set covers it.

U = {1, 2, 3, 4, 5, 6}, S₁ = {1, 2, 3, 4}, S₂ = {1, 2, 5}, S₃ = {3, 4, 6}. Greedy picks S₁ (4 new elements), then needs both S₂ and S₃ for 5 and 6: three sets. But S₂ and S₃ alone cover everything: two sets.

Answer & reasoning

Step by step

1. Collect the digits used in the cell’s row, column and 3×3 box.
2. Offer only 1,…,9 minus that union. Zero candidates means this branch cannot succeed.
3. Choose an empty cell with the fewest candidates next. This is a heuristic for finding conflicts early, not a guarantee of polynomial search.

for the next empty cell, the candidates are the digits 1 to 9 not already present in that cell’s row, column and 3 × 3 box; compute them by scanning those 20 neighbours. The trick: instead of filling cells in a fixed order, always choose next the empty cell with the fewest candidates (often just one), which forces contradictions to surface early and keeps the search tree narrow.

Answer & reasoning

Step by step

1. Let p(i) be the last earlier job ending no later than job i starts; use half-open intervals.
2. Skipping earns OPT(i−1). Taking earns feeᵢ+OPT(p(i)), because only that compatible prefix remains available.
3. Set OPT(0)=0 and keep the larger amount. Sorting and binary-searching all predecessors cost O(n log n); filling the table costs O(n).

Sort jobs by finish time and let p(i) be the last earlier job compatible with job i, found by binary search. For half-open intervals, compatibility means finish ≤ start. Set OPT(0) = 0 and OPT(i) = max(OPT(i−1), feeᵢ + OPT(p(i))). The first branch skips the job; the second includes it and the best compatible prefix. Sorting and predecessor searches take O(n log n); the DP itself takes O(n).

Answer & reasoning

Step by step

1. Initially only sum 0 is reachable with no items.
2. Use can[i,t]=can[i−1,t] OR can[i−1,t−sᵢ], with the second branch allowed only if t≥sᵢ.
3. There are (n+1)(T+1) cells. A target such as T=2ᵇ has only b+1 binary digits but needs roughly 2ᵇ columns. That is why O(nT) is pseudo-polynomial.

Let can[i,t] mean that a subset of the first i positive numbers sums to t. Set can[0,0] true and can[0,t] false for t > 0. Use can[i,t] = can[i−1,t] or (t ≥ sᵢ and can[i−1,t−sᵢ]). The table takes O(nT) time. This is polynomial in the numeric value T, not in its bit length log₂ T; binary-encoded inputs can make T exponentially large. This is pseudo-polynomial time.

Answer & reasoning

a translation of every instance of problem A into an instance of problem B that preserves the yes/no answer, computable in polynomial time. If A is hard, then B is at least as hard (a fast B would give a fast A). Fast algorithms travel the other way, from B to A.

Answer & reasoning

P: problems solvable in polynomial time. NP: problems for which a proposed yes-answer can be checked in polynomial time. NP-complete: problems in NP to which every problem in NP reduces, so they are the hardest problems in NP.

Answer & reasoning

given a proposed truth assignment, you can check every clause in time linear in the size of the formula.

Answer & reasoning

y = true and z = true satisfy all three clauses whatever x is.

Answer & reasoning

no: x would have to be both true and false. Yes: one literal of {x, ¬x} is always true.

Answer & reasoning

given a weighted graph, two vertices s and t, and a number k, is there a path from s to t of total weight at most k?

Answer & reasoning

2, for example {2, 3}: it touches the edges 1–2, 2–3 and 3–4. One vertex cannot touch all three edges.

Answer & reasoning

2, for example {1, 3}, {1, 4} or {2, 4}. This is 4 − 2, the complement of a minimum vertex cover.

Answer & reasoning

3 (the whole triangle); 2 (any single edge; no three vertices are mutually adjacent).

Answer & reasoning

The decision versions of longest simple path, Hamiltonian circuit and vertex cover are NP-complete. Unweighted or nonnegative-weight shortest-path decision, Eulerian-circuit existence, and edge-cover decision have polynomial algorithms. Keep the input assumptions and decision/optimisation distinction explicit.

Answer & reasoning

2-SAT is in P. The chain construction for proving hardness needs a spare slot in each clause to hold a linking variable, and clauses of size 2 have none, so it does not apply; 3-SAT is NP-complete.

Answer & reasoning

whether every problem whose answers can be checked quickly can also be solved quickly. Nobody knows; it is the biggest open problem in computer science.

Answer & reasoning

3-SAT (the general-purpose choice), integer partition (targets whose hardness involves large numbers), vertex cover (graph problems about selecting a subset), Hamiltonian path (graph problems about ordering or routing).

Answer & reasoning

P = NP: every problem in NP reduces to vertex cover in polynomial time, so all of them, including SAT, TSP and the rest, would have polynomial algorithms.

Answer & reasoning

Introduce v and use (a ∨ b ∨ v) ∧ (¬v ∨ c ∨ d). If a or b is true, choose v = false: the first clause is already satisfied and ¬v satisfies the second. Otherwise, if c or d is true, choose v = true: v satisfies the first and c or d satisfies the second. If all four original literals are false, the two clauses require v and ¬v simultaneously. Thus the new formula is satisfiable exactly when the original clause is.

Answer & reasoning

with new variables v₁, v₂: {a, v₁, v₂}, {a, v₁, ¬v₂}, {a, ¬v₁, v₂}, {a, ¬v₁, ¬v₂}. Every combination of v₁, v₂ falsifies the other two literals of one clause, so only a = true satisfies all four.

Answer & reasoning

if S is a vertex cover, no edge has both endpoints outside S (such an edge would be uncovered), so V − S is independent. If I is independent, every edge has at most one endpoint in I, hence at least one in V − I, so V − I is a cover. The sizes are complementary.

Answer & reasoning

the complement has exactly the missing edges, 1–3 and 2–4. The independent set {1, 3} of the cycle is an edge, that is a clique of size 2, in the complement; likewise {2, 4}.

Answer & reasoning

subset sum: the certificate is the subset; add it up and compare with t, polynomial time. TSP: the certificate is the tour; check it visits every city once and add its edge weights, polynomial time.

Answer & reasoning

A polynomial reduction X → SAT gives a method for solving X using a SAT solver; it establishes membership in NP for an ordinary polynomial many-one reduction to SAT, not NP-hardness of X. To prove X NP-hard, reduce a known NP-complete problem to X. To conclude NP-completeness, also establish that X is in NP. A SAT solver is not assumed to take exponential time on every input.

Answer & reasoning

the special case k = n − 1 asks whether G has a path through all n vertices, which is exactly the Hamiltonian path problem, known to be NP-complete. A problem with an NP-complete special case is NP-complete (membership in NP: the path is a checkable certificate).

Answer & reasoning

Use integer variables X, X̄, Y, Ȳ, Z, Z̄ in {0,1}. Require X + X̄ = Y + Ȳ = Z + Z̄ = 1 and X + Ȳ + Z ≥ 1. The last inequality says at least one literal is true. Integrality is essential: allowing arbitrary fractions in [0,1] would not encode Boolean truth values.

Answer & reasoning

Check that every vertex is assigned one of the three allowed colours, then check each edge has differently coloured endpoints: O(n + m). This puts the decision problem in NP. Deciding whether such a colouring exists is NP-complete; finding a colouring is the associated search task.

Answer & reasoning

if you can solve the problem in polynomial time, you can check any proposed answer in polynomial time simply by ignoring it, solving from scratch, and comparing.

Answer & reasoning

build the complement graph Ḡ (same vertices, an edge exactly where G has none), which takes O(n²), and ask for a clique of size k in Ḡ. A set is independent in G if and only if it is a clique in Ḡ.

Answer & reasoning

let the universe be the set of edges of G, and for each vertex v make the subset Sᵥ of edges touching v. A collection of k subsets covers all edges exactly when the corresponding k vertices form a vertex cover. Set cover is in NP (a proposed collection is easy to check), so it is NP-complete.

Answer & reasoning

A proposed tour is checked by verifying the visits and adding its edge weights, then comparing with the bound; this takes polynomial time in the encoded input. Finding a qualifying tour requires an algorithm to select one. Exhaustive enumeration is one method, but is not known to be necessary. No polynomial-time exact algorithm for general TSP is known; that is not a proof that every method must enumerate all tours.

Answer & reasoning

let X be NP-complete and in P. Every problem Y in NP reduces to X in polynomial time. To solve Y: translate the instance to X (polynomial), solve X (polynomial), return the answer. Two polynomials compose to a polynomial, so Y is in P. Hence NP ⊆ P, and with P ⊆ NP always, P = NP. Equally, proving that one NP-complete problem needs exponential time would prove P ≠ NP.

Answer & reasoning

Step by step

1. Original total W plus new weights 2W−t and W+t gives total 4W; each half must weigh 2W.
2. The two new weights together are 3W, so they cannot share a half.
3. The half containing 2W−t needs exactly t from the original items. This proves both directions, and the numbers have polynomial bit length. Finally, checking a proposed partition is polynomial, giving NP membership.

Use positive-integer subset sum with total W > 0 and 0 ≤ t ≤ W; targets outside the range can be handled directly. Add two labelled items of weights 2W − t and W + t. The total is 4W, so equal halves each weigh 2W. The new items cannot share a half because together they weigh 3W > 2W. The half containing 2W − t needs original items totalling exactly t. Conversely such a subset determines a partition. Labels preserve distinct items even when weights coincide. The transformation has polynomial bit length; a proposed partition is easy to verify.

Answer & reasoning

Step by step

1. For an undirected graph with at least two vertices, add z and edges from z to all original vertices.
2. An original Hamiltonian path u→…→v becomes the cycle z→u→…→v→z.
3. Conversely, delete z from any Hamiltonian cycle of the new graph to get a path through every old vertex. Tiny inputs can be handled separately; a cycle certificate is polynomial to check.

given G, add a new vertex z joined to every vertex of G, giving G′. If G has a Hamiltonian path from u to v, then z–u–…–v–z is a Hamiltonian cycle of G′. Conversely a Hamiltonian cycle of G′ passes through z once; deleting z leaves a path through every vertex of G. Membership in NP is clear (the cycle is the certificate).

Answer & reasoning

Step by step

1. With two colours, each neighbour has just one allowed colour.
2. With three, each neighbour may have two allowed colours, and choices can interact across distant edges.
3. Thus the forced BFS procedure no longer solves every case. This explains why that argument fails, not why every possible algorithm must be exponential.

With two colours, choosing a component’s first colour forces every neighbour to use the other colour; BFS can detect a conflict. With three colours, a neighbour can have two choices, and those choices affect later edges. The simple forced-colouring argument therefore fails. Backtracking may explore exponentially many choices, but that is not a proof that every possible algorithm must take exponential time.

Answer & reasoning

Step by step

1. Pick an uncovered edge, add both endpoints, and discard every edge now covered. Continue until none remain.
2. Chosen edges have no shared endpoints, so they form a matching of size r. Every cover needs at least r vertices.
3. Your cover uses exactly 2r vertices, hence at most twice optimum. “Maximal” means no more disjoint edges can be added; it need not be the largest matching.

while some edge is uncovered, pick one and put both its endpoints into the cover. The chosen edges share no endpoints (each new edge was uncovered by all earlier endpoints), so they form a matching M. Any vertex cover, including the optimal one, must contain at least one endpoint of every edge of M, so OPT ≥ |M|. Our cover has exactly 2|M| vertices, hence at most 2 × OPT.

Answer & reasoning

Step by step

1. Therefore the MST weight is at most the optimal tour length.
2. Traverse each tree edge in both directions: a closed walk of length 2·MST visits every vertex.
3. Skip repeated vertices. Triangle inequality ensures a direct shortcut is no longer than the replaced detour. The resulting tour costs at most 2·OPT.

remove one edge from the optimal tour: what remains is a spanning tree, so MST ≤ OPT. Doubling every MST edge gives a closed walk that visits all vertices with length 2 × MST ≤ 2 × OPT. Walk it, skipping vertices already visited; by the triangle inequality each shortcut is no longer than the detour it replaces, so the resulting tour is at most 2 × MST ≤ 2 × OPT.

Answer & reasoning

Step by step

1. A satisfying assignment is a short witness: check every clause.
2. For unsatisfiability, no universal polynomial-size certificate with a polynomial-time checker is known; restricted cases may still have easy proofs.
3. UNSAT belongs to co-NP. Whether it also belongs to NP is unresolved and equivalent to NP=co-NP. Do not turn “unknown” into “impossible.”

No general polynomial-size, polynomially checkable certificate for unsatisfiability is known. Such certificates do exist for some restricted formulas. UNSAT is in co-NP because its no-instances have satisfying assignments as certificates. Whether UNSAT is also in NP is equivalent to NP = co-NP and remains open; exhaustive enumeration is one method, not a proven necessity.

Answer & reasoning

Step by step

1. There are 3 variable edges: 6 vertices. Two clause triangles add 6 more, giving 12; the target is 3+2·2=7.
2. Select variable vertices x,y,z. In triangle (x,y,¬z), leave x out and select y,¬z. In triangle (¬x,y,z), leave y out and select ¬x,z.
3. Each variable edge is covered; two vertices cover every triangle edge. A skipped clause vertex has its same-literal variable endpoint selected, so its cross edge is covered too.

n = 3 variables and c = 2 clauses give 2·3 + 3·2 = 12 vertices and a target cover size of n + 2c = 7. Variable gadgets: take the true literals x, y, z (3 vertices). Clause triangle {x, y, ¬z}: its x-vertex’s cross edge is already covered from the variable side (x is true), so take the other two, the y-vertex and the ¬z-vertex. Triangle {¬x, y, z}: y is true, so take the ¬x-vertex and the z-vertex. Total 3 + 2 + 2 = 7 vertices, covering every variable edge, every triangle edge and every cross edge.