# Question 13683: Reflexive Connectivity Includes a Length-Zero Path

[Return to catalogue page 69](https://ocme.evemisslab.com/en/questions/page/69/)

[← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261014-advance-20261028-r07-connected-component-foundations/#q-20261014-advance-20261028-r07-connected-component-0058)

This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth.

R0026-13683 · q-20261014-advance-20261028-r07-connected-component-0058



## Original question and givens

Use the complete finite undirected loop-free simple graph on Fin(7)={0,…,6} with edge set=[[0, 4], [0, 5], [0, 6], [1, 2], [1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4]]. Loops and duplicate undirected edges are forbidden. Connectivity is complete path reachability, not just one traversal fragment. Length-zero paths make every vertex reachable from itself, including isolated vertices. Do not switch to directed weak/strong, infinite or dynamic connectivity. left=0, right=1. Give (left,right,left_component,same_component?).


- G001 — Use the complete finite undirected loop-free simple graph on Fin(7)={0,…,6} with edge set=[[0, 4], [0, 5], [0, 6], [1, 2], [1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4]]. Loops and duplicate undirected edges are forbidden. Connectivity is complete path reachability, not just one traversal fragment. Length-zero paths make every vertex reachable from itself, including isolated vertices. Do not switch to directed weak/strong, infinite or dynamic connectivity. left=0, right=1. Give (left,right,left_component,same_component?).





## Definition and scope

Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.


- [mko-connected-component](https://ocme.evemisslab.com/en/mko/mko-connected-component/)





## Step-by-step derivation

S001 · impliesBefore

full carrier Fin(7);raw undirected edges=[[0, 4], [0, 5], [0, 6], [1, 2], [1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4]]

After

canonical simple edges=[[0, 4], [0, 5], [0, 6], [1, 2], [1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4]];full adjacency rows=[[4, 5, 6], [2, 4, 5, 6], [1, 4, 5, 6], [4], [0, 1, 2, 3], [0, 1, 2], [0, 1, 2]]

Conditions: none

Build adjacency on the full carrier,rejecting loops and duplicate undirected edges.Vertices absent from edges retain empty rows;do not switch to directed connectivity.

Step identifiers and dependenciesRule: component_full_undirected_graph_includes_isolates · Uses: G001





S002 · impliesBefore

left vertex:start vertex=0;complete adjacency=[[4, 5, 6], [2, 4, 5, 6], [1, 4, 5, 6], [4], [0, 1, 2, 3], [0, 1, 2], [0, 1, 2]]

After

initial visited=[0];path to start=[0];edge length0

Conditions: none

The start reaches itself by a length-zero path.Even an isolated vertex must be included rather than omitted for having no edges.

Step identifiers and dependenciesRule: component_zero_length_reflexive_path · Uses: G001, S001





S003 · impliesBefore

left vertex:layer=0;frontier=[0];all frontier neighbors=[4, 5, 6]

After

previously seen=[0];new vertices=[4, 5, 6]

Conditions: none

At each layer inspect every neighbor of every frontier vertex,then add only unvisited distinct labels.Do not stop at a plausible-looking fragment.

Step identifiers and dependenciesRule: component_complete_frontier_expansion · Uses: G001, S002





S004 · impliesBefore

left vertex:new vertex=4;earliest frontier parent=0;parent path=[0]

After

append actual parent edge;reachable path=[0, 4]

Conditions: none

Extend the established parent path by an original graph edge,so every added vertex really is reachable.

Step identifiers and dependenciesRule: component_each_new_vertex_path_witness · Uses: G001, S003





S005 · impliesBefore

left vertex:new vertex=5;earliest frontier parent=0;parent path=[0]

After

append actual parent edge;reachable path=[0, 5]

Conditions: none

Extend the established parent path by an original graph edge,so every added vertex really is reachable.

Step identifiers and dependenciesRule: component_each_new_vertex_path_witness · Uses: G001, S004





S006 · impliesBefore

left vertex:new vertex=6;earliest frontier parent=0;parent path=[0]

After

append actual parent edge;reachable path=[0, 6]

Conditions: none

Extend the established parent path by an original graph edge,so every added vertex really is reachable.

Step identifiers and dependenciesRule: component_each_new_vertex_path_witness · Uses: G001, S005





S007 · impliesBefore

left vertex:layer=1;frontier=[4, 5, 6];all frontier neighbors=[0, 1, 2, 3]

After

previously seen=[0, 4, 5, 6];new vertices=[1, 2, 3]

Conditions: none

At each layer inspect every neighbor of every frontier vertex,then add only unvisited distinct labels.Do not stop at a plausible-looking fragment.

Step identifiers and dependenciesRule: component_complete_frontier_expansion · Uses: G001, S006





S008 · impliesBefore

left vertex:new vertex=1;earliest frontier parent=4;parent path=[0, 4]

After

append actual parent edge;reachable path=[0, 4, 1]

Conditions: none

Extend the established parent path by an original graph edge,so every added vertex really is reachable.

Step identifiers and dependenciesRule: component_each_new_vertex_path_witness · Uses: G001, S007





S009 · impliesBefore

left vertex:new vertex=2;earliest frontier parent=4;parent path=[0, 4]

After

append actual parent edge;reachable path=[0, 4, 2]

Conditions: none

Extend the established parent path by an original graph edge,so every added vertex really is reachable.

Step identifiers and dependenciesRule: component_each_new_vertex_path_witness · Uses: G001, S008





S010 · impliesBefore

left vertex:new vertex=3;earliest frontier parent=4;parent path=[0, 4]

After

append actual parent edge;reachable path=[0, 4, 3]

Conditions: none

Extend the established parent path by an original graph edge,so every added vertex really is reachable.

Step identifiers and dependenciesRule: component_each_new_vertex_path_witness · Uses: G001, S009





S011 · impliesBefore

left vertex:layer=2;frontier=[1, 2, 3];all frontier neighbors=[1, 2, 4, 5, 6]

After

previously seen=[0, 1, 2, 3, 4, 5, 6];new vertices=[]

Conditions: none

At each layer inspect every neighbor of every frontier vertex,then add only unvisited distinct labels.Do not stop at a plausible-looking fragment.

Step identifiers and dependenciesRule: component_complete_frontier_expansion · Uses: G001, S010





S012 · impliesBefore

left vertex:final visited=[0, 1, 2, 3, 4, 5, 6];all [vertex,neighbors,outside neighbors] rows=[[0, [4, 5, 6], []], [1, [2, 4, 5, 6], []], [2, [1, 4, 5, 6], []], [3, [4], []], [4, [0, 1, 2, 3], []], [5, [0, 1, 2], []], [6, [0, 1, 2], []]]

After

no edge leaves visited;every visited vertex has a path;visited equals full reachable set

Conditions: none

Path witnesses give visited⊆reachable.At completion no edge leaves visited.If a path reached outside,it would have a first leaving edge,a contradiction,so reachable⊆visited.Both directions establish the whole component,not a traversal order.

Step identifiers and dependenciesRule: component_reachable_and_closed_set_completeness · Uses: G001, S011





S013 · impliesBefore

left=0;right=1;whole left component=[0, 1, 2, 3, 4, 5, 6]

After

same component=Yes

Conditions: none

Compute the whole left component before testing the right label.Equal endpoints are connected by a zero-length path even if isolated.

Step identifiers and dependenciesRule: component_membership_after_complete_reachability · Uses: G001, S012









## Reverse checks


- S013 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S012 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S009 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S007 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S003 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.





## Result

(0, 1, [0, 1, 2, 3, 4, 5, 6], Yes)

The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.





## This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.

Source hashes and review receipts
- input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
- original question SHA-256: f2349ed2968643183a84dd4d845e36c00832884cfc53b57ddd35211b919a3ec8
- candidate record SHA-256: 6c74ea9ac14a613f2f0d2d7b8a9075dd19ac95810a76694c3a1b701863b54e94
- semantic review receipt SHA-256: f335caca08574c9f949c141083c66655fee51c227d45d80a3ddb7d78f862d798
- question-first witness SHA-256: cc7ba54738af91a6871fc1c20e45ad8f2b434392273fa334bd16a3b2238f4a77
- Lean: NOT_RUN · human review: NOT_PERFORMED

[Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261014-advance-20261028-r07-connected-component-0058.json)