Recognize minimal connected structure

Try

A chain of four vertices is connected and has three edges. Adding an edge between its ends creates a cycle. Removing any original edge before adding that extra edge disconnects the chain. These are characteristic features of a tree.

Predict

Predict the distinction between walk and path. A walk follows edges and may repeat vertices; a simple path has no repeated vertices. A cycle returns to its start with no other repeated vertices. A tree is connected and acyclic; a forest is acyclic but may have several components.

Experiment

Draw a five-vertex tree and trace the unique path between two selected vertices. Add an edge between previously nonadjacent vertices and identify the cycle it creates. Then remove one edge of that cycle and check that the graph is connected again.

Understand

Worked proof of uniqueness: connectivity supplies a path between two vertices. If two different simple paths existed, follow them to a divergence and then their next reunion; the two segments would form a cycle. Acyclicity therefore forces a unique path.

A finite tree with n vertices has n−1 edges. For n>1, a longest simple path ends at a leaf: an extra neighbor would extend it or create a cycle. Removing a leaf leaves a smaller tree, so induction adds one edge for each new vertex. Summing across c components gives a forest with n−c edges.

Invalid classification: n−1 edges alone proves a graph is a tree. A triangle plus an isolated vertex has four vertices and three edges but is disconnected and cyclic.

Apply

Use both structural conditions. To prove a graph is a tree, connectedness plus n−1 edges is sufficient for a finite simple graph, but the edge count cannot replace connectedness. Justify any use of an equivalent characterization.

Two paths guarantee a cycle somewhere, not necessarily at your endpoints

All graphs in this section are finite, simple and undirected. A simple cycle has at least three edges and repeats only its first vertex at the end. Two distinct simple paths from u to v do imply a cycle somewhere in their union. Follow their common initial segment to its last vertex s. Then follow one path to the first subsequent vertex t lying on the other path. Its interior has no vertex on the other path. The two s-to-t segments therefore form a simple cycle. The divergence and reunion need not be u and v.

For a concrete counterexample, use edges 0–1, 1–2, 1–3, 2–4, 3–4 and 4–5. There are two simple paths from0 to5: through2 or through3. Their divergence is1 and reunion4, giving cycle1–2–4–3–1. Vertices0 and5 each have degree one, so neither can lie on any simple cycle. A proof must preserve the requested endpoints, not merely find an unrelated cycle.

Where does the cycle actually pass?

Graph and endpointsDiamond with terminal stemsSame graph, endpoints inside the diamondTwo triangles sharing an articulationReset endpoint comparison

Selected endpoints u=0, v=5. Predict whether one simple cycle contains both. The graph does contain the cycle 1–2–4–3–1; that alone does not answer the endpoint question.

First path0–1–2–4–50–1–3–4–5Second path0–1–2–4–50–1–3–4–5

Solid navy first path: 0–1–2–4–5. Dashed red second: 0–1–3–4–5. Shared internal vertices: 1, 4. Distinct paths: yes. Edge-disjoint: no.

This pair does not certify a simple cycle through both endpoints. Shared internal vertices or choosing the same path invalidate that construction.

Compare with the exhaustive bounded audit

All 2 simple paths and 1 distinct path pairs were checked. No internally vertex-disjoint pair exists; the proved equivalence therefore rules out a simple cycle through both endpoints. Completeness follows because depth-first enumeration explores every unused next vertex, stopping at the target; no repeated vertex is allowed. This is a bounded exhaustive certificate, not an efficient algorithm for arbitrarily large graphs.

Three fixed cases with at most six vertices. The general six-vertex cap permits at most65 simple paths per endpoint pair. State is temporary; written tasks require a structural proof beyond reading this result.

The exact endpoint criterion

For distinct vertices u and v, a simple cycle contains both if and only if there are two distinct simple u-to-v paths with no common internal vertex. An internal vertex is any vertex of a path other than its two endpoints. This is stronger than the paths merely being distinct, or merely having disjoint edge sets.

If a simple cycle contains u and v, cut it at these two vertices. Its two arcs are simple paths and share only the endpoints, since the original cycle has no repeated vertex. Conversely, follow one of two internally vertex-disjoint simple paths from u to v and the other backwards from v to u. The only repeated vertex is u at the closing step: no repetition occurs inside either path and their interiors do not intersect. Distinctness matters if both paths are the same single edge. In a simple graph two distinct paths with disjoint interiors give at least three edges in their union. Thus the concatenation is a simple cycle through the specified endpoints. This proves both directions without invoking a general connectivity theorem.

Edge-disjoint paths can still share a bottleneck

Take two triangles sharing only vertex0: edges0–1,1–2,2–0 and0–3,3–4,4–0. The paths1–0–3 and1–2–0–4–3 have no common edge, but both contain the internal vertex0. Removing0 separates1 from3. Every path between these endpoints must therefore use0, so two internally vertex-disjoint paths are impossible. By the proved criterion, no simple cycle contains both1 and3, although each endpoint separately lies on a triangle.

More generally, if w differs from u and v and they lie in different components after deleting w, every u-to-v path contains w internally. This is an exact obstruction certificate. Do not reverse it into a general theorem without proof: the present lesson proves the obstruction and the two-path/cycle equivalence, not the full collection of vertex-connectivity theorems. A repeated-vertex closed walk through both endpoints also does not qualify as a simple cycle.

Why the finite explorer's negative result is more than a sampled failure

Its depth-first enumeration starts at u and extends a path by every adjacent vertex not already on it. It records and stops at v. Any simple u-to-v path appears by successively following exactly its vertex choices; no path is lost because its next vertex has not occurred earlier. Conversely every recorded sequence is a simple path with the right endpoints. Comparing all distinct pairs therefore decides the endpoint criterion for the displayed finite graph. With at most six vertices there are at most four internal vertices available; all ordered selections of these give at most65 paths. This small complete enumeration is bounded teaching computation, not a claim of scalability. The structural articulation or degree argument remains the transferable proof.

This addresses the endpoint-sensitive witness requirement retained in the Spring2015 MIT6.042J third-midterm audit. The labelled examples and changed branch construction are original. Write the requested witness or obstruction and explain where the endpoints enter the proof; a count of successful path traces is not independent learner mastery.

A vertex-order certificate for a forest

A different way to certify tree structure is to order the vertices so that each has at most one neighbor earlier in the order. This is an ordering condition, not the antichain width of a precedence order. The existing greedy-coloring lesson proves the more general deletion-order coloring argument; here we construct and count the exact tree orders required by the source task.

Every finite forest admits such an order. Induct on its vertex count, including the empty forest. A nonempty forest has an isolated vertex or a leaf in some nontrivial component: a longest path in that component has a leaf endpoint. Remove such a vertex v. The remaining graph is a forest and has an order by induction. Append v last. Earlier vertices retain exactly their old earlier neighbors, while v has at most its one original neighbor earlier. Thus the property is preserved. If you repeatedly delete leaves to construct the order, reverse the deletion list; using the deletion list forwards need not work.

Conversely, if a graph contains a cycle, choose the cycle vertex occurring last in any proposed order. Its two distinct cycle neighbors both occur earlier, violating the condition. Therefore a finite simple undirected graph admits an at-most-one-earlier-neighbor order exactly when it is a forest. A tree is the connected special case; the condition alone does not establish connectedness.

Choose an order, then check every earlier neighbor

TreeBranched six-vertex treeFive-vertex pathFive-vertex star Declared first vertex r012345

Edges: 0–1, 0–2, 1–3, 1–4, 2–5. Start from the supplied parent-before-child order, then swap two neighboring positions and predict which certificate changes.

Positions to exchange1 and 22 and 33 and 44 and 55 and 6Swap adjacent positionsRestore rooted orderReset tree investigation

At most one earlier neighbor at every vertex: yes. First vertex equals declared root 0: yes. These are separate checks.

• Vertex 0: earlier neighbors none.
• Vertex 1: earlier neighbors 0.
• Vertex 2: earlier neighbors 0.
• Vertex 3: earlier neighbors 1.
• Vertex 4: earlier neighbors 1.
• Vertex 5: earlier neighbors 2.

Count all orders with this first vertex

Rooted subtree sizes in vertex order: 6, 3, 2, 1, 1, 1. Their product is 36; n!=720. The proved quotient gives 20 valid orders starting at 0.

These counts follow from the interleaving proof, not from assuming all vertex permutations work. Independent developer tests enumerate every permutation of the bounded trees, but that finite verification does not replace the general argument.

Three fixed trees, at most six vertices, temporary state. No completion or proof-quality credit is awarded by a passing order check.

Once the first vertex is fixed, the order must respect the rooted tree

Let T be a nonempty tree and let r be the first vertex of an admissible order. Each of its n−1 edges contributes once to the earlier-neighbor count, at its later endpoint. All n counts are at most one and the first is zero, so every later vertex has exactly one earlier neighbor. Consequently every prefix of the order is connected: each next vertex joins the preceding prefix through that neighbor.

Root the tree at r. The parent of a vertex v is the neighbor on its unique path toward r. Following earlier neighbors from v strictly decreases order positions and ends at r. This gives the unique path from v to r, so its first edge goes to the parent. Therefore each parent appears before its children. Conversely, in any parent-before-child order the root has no earlier neighbor and every other vertex has exactly its parent earlier, since its other neighbors are children. This proves an exact characterization, not only a way to generate some orders.

Count the admissible orders rather than guessing from permutations

For each vertex v, let s_v be the number of vertices in its rooted subtree, including v. The number of admissible orders beginning at r is n! divided by the product of all s_v. For one vertex it is one. For a larger tree, let the root’s child subtrees have sizes n₁,…,n_k. The root is first. Choose the positions of each subtree among the remaining n−1 positions: the number is (n−1)! divided by the product of the n_i factorials. Within each subtree, induction gives n_i! divided by its own subtree-size product. Multiplication cancels the subtree factorials. The result is (n−1)! divided by the product of all nonroot subtree sizes, which equals n! divided by the product including s_r=n.

Every parent-before-child order decomposes uniquely into these chosen positions and within-subtree orders, so the count neither misses nor double-counts arrangements. The formula depends on the chosen root. For a five-vertex star, beginning at the center allows all four leaves in any order, giving24. Beginning at a specified leaf forces that leaf first and the center second, then permits the remaining three leaves in any order, giving6. There is no contradiction: a valid ordering can start at a different root and therefore fall outside the count currently being requested.

Why this is more than the existing coloring bound

Reverse deletion in a forest also produces a two-color greedy order. The present certificate proves the forest converse, characterizes every valid order for a fixed first vertex, and counts those orders. A two-coloring alone is weaker: an even cycle is two-colorable but has no at-most-one-earlier-neighbor order. Its last cycle vertex supplies the obstruction regardless of coloring.

The Spring2015 MIT6.042J final tree-ordering item supplies the retained ordering-construction requirement. The rooted counting proof and changed branch examples extend that capability with original practice. Exact finite order checks support a learner’s argument; they do not assess the proof automatically.

Continue

Depth: every connected finite graph has a spanning tree, obtained by deleting cycle edges without breaking connectivity. Breadth-first search produces one with shortest-path distances from a chosen root. Weighted minimum spanning trees are a separate optimization problem.

Trace a real queue in the breadth-first search investigation.