# Question 18904: Degree Parity Needs Connected Nonisolated Support [Return to catalogue page 95](https://ocme.evemisslab.com/en/questions/page/95/) [← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261014-advance-20261105-r04-eulerian-trail-foundations/#q-20261014-advance-20261105-r04-eulerian-trail-0029) 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. R0036-18904 · q-20261014-advance-20261105-r04-eulerian-trail-0029 ## Original question and givens Use the complete finite simple undirected graph on Fin(5)={0,…,4}, with canonical sorted edges=[[0, 1], [1, 2], [2, 3], [3, 4]] and zero-based edge indices in that order. The edge support contains exactly the nonisolated vertices. A trail may revisit vertices but may not repeat an edge; an Euler trail uses every edge once. Isolated vertices do not invalidate connected edge support, and no Hamiltonian conclusion follows. Give (degrees, odd_vertices, edge_support_connected, euler_type, criterion). - G001 — Use the complete finite simple undirected graph on Fin(5)={0,…,4}, with canonical sorted edges=[[0, 1], [1, 2], [2, 3], [3, 4]] and zero-based edge indices in that order. The edge support contains exactly the nonisolated vertices. A trail may revisit vertices but may not repeat an edge; an Euler trail uses every edge once. Isolated vertices do not invalidate connected edge support, and no Hamiltonian conclusion follows. Give (degrees, odd_vertices, edge_support_connected, euler_type, criterion). ## 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-eulerian-trail](https://ocme.evemisslab.com/en/mko/mko-eulerian-trail/) ## Step-by-step derivation S001 · impliesBefore source operation=euler-odd-degree-classification;original snapshot and mathematics retained After explicit ordered source output fields=[degrees, odd_vertices, edge_support_connected, euler_type, criterion] Conditions: none Keep the historical interface marker in the original snapshot while listing the original ordered fields here.No JavaScript or external table is needed for the main text,and field labels are not mathematical evidence. Step identifiers and dependenciesRule: source_ordered_interface_explicit_without_javascript · Uses: G001 S002 · impliesBefore complete ORIGINAL carrier Fin(5);canonical ORIGINAL simple undirected edges=[[0, 1], [1, 2], [2, 3], [3, 4]] After edge indices are EXACT original list positions0..3;retain ALL vertices;no12-vertex or10-edge bound Conditions: none Keep edge indices at their original numeric positions,not string-sorted vertex pairs.This family permits up to60 vertices rather than importing earlier bounds;empty-edge graphs appear only where the operation allows them. Step identifiers and dependenciesRule: euler_original_simple_graph_indices_full_carrier · Uses: G001, S001 S003 · calculationBefore Euler vertex0 exact incident edge count := sum(1) After Euler vertex0 exact incident edge count = 1 Conditions: none Substitute original data and established intermediates exactly,retaining indices,signs and the relevant space. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S002 S004 · impliesBefore original vertex=0;ALL original incident edge indices=[0] After degree=1;nonisolated=Yes;odd=Yes Conditions: none Count this vertex's incident edges in the complete original list.Retain degree0 vertices in the full carrier;neither vertex labels nor support size are degrees. Step identifiers and dependenciesRule: euler_degree_actual_incidence_not_label_or_support_size · Uses: G001, S003 S005 · calculationBefore Euler vertex1 exact incident edge count := sum(1, 1) After Euler vertex1 exact incident edge count = 2 Conditions: none Substitute original data and established intermediates exactly,retaining indices,signs and the relevant space. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S004 S006 · impliesBefore original vertex=1;ALL original incident edge indices=[0, 1] After degree=2;nonisolated=Yes;odd=No Conditions: none Count this vertex's incident edges in the complete original list.Retain degree0 vertices in the full carrier;neither vertex labels nor support size are degrees. Step identifiers and dependenciesRule: euler_degree_actual_incidence_not_label_or_support_size · Uses: G001, S005 S007 · calculationBefore Euler vertex2 exact incident edge count := sum(1, 1) After Euler vertex2 exact incident edge count = 2 Conditions: none Substitute original data and established intermediates exactly,retaining indices,signs and the relevant space. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S006 S008 · impliesBefore original vertex=2;ALL original incident edge indices=[1, 2] After degree=2;nonisolated=Yes;odd=No Conditions: none Count this vertex's incident edges in the complete original list.Retain degree0 vertices in the full carrier;neither vertex labels nor support size are degrees. Step identifiers and dependenciesRule: euler_degree_actual_incidence_not_label_or_support_size · Uses: G001, S007 S009 · calculationBefore Euler vertex3 exact incident edge count := sum(1, 1) After Euler vertex3 exact incident edge count = 2 Conditions: none Substitute original data and established intermediates exactly,retaining indices,signs and the relevant space. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S008 S010 · impliesBefore original vertex=3;ALL original incident edge indices=[2, 3] After degree=2;nonisolated=Yes;odd=No Conditions: none Count this vertex's incident edges in the complete original list.Retain degree0 vertices in the full carrier;neither vertex labels nor support size are degrees. Step identifiers and dependenciesRule: euler_degree_actual_incidence_not_label_or_support_size · Uses: G001, S009 S011 · calculationBefore Euler vertex4 exact incident edge count := sum(1) After Euler vertex4 exact incident edge count = 1 Conditions: none Substitute original data and established intermediates exactly,retaining indices,signs and the relevant space. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S010 S012 · impliesBefore original vertex=4;ALL original incident edge indices=[3] After degree=1;nonisolated=Yes;odd=Yes Conditions: none Count this vertex's incident edges in the complete original list.Retain degree0 vertices in the full carrier;neither vertex labels nor support size are degrees. Step identifiers and dependenciesRule: euler_degree_actual_incidence_not_label_or_support_size · Uses: G001, S011 S013 · impliesBefore nonisolated edge support:original edge index=0;edge=[0, 1];from=0;new vertex=1 After original-edge path from0=[0, 1];reached=[0, 1] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S012 S014 · impliesBefore nonisolated edge support:original edge index=1;edge=[1, 2];from=1;new vertex=2 After original-edge path from0=[0, 1, 2];reached=[0, 1, 2] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S013 S015 · impliesBefore nonisolated edge support:original edge index=2;edge=[2, 3];from=2;new vertex=3 After original-edge path from0=[0, 1, 2, 3];reached=[0, 1, 2, 3] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S014 S016 · impliesBefore nonisolated edge support:original edge index=3;edge=[3, 4];from=3;new vertex=4 After original-edge path from0=[0, 1, 2, 3, 4];reached=[0, 1, 2, 3, 4] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S015 S017 · impliesBefore nonisolated edge support:complete permitted carrier=[0, 1, 2, 3, 4];reached=[0, 1, 2, 3, 4];unreached=[];ALL original edges=[[0, 1], [1, 2], [2, 3], [3, 4]] After no edge in carrier crosses reached/unreached cut;connected=Yes Conditions: none Exhausting BFS proves no edge crosses the cut,so an unreached vertex has no path from the start;otherwise path witnesses cover the carrier.Audit support and full carrier separately without silently deleting isolates to claim whole-graph connectivity. Step identifiers and dependenciesRule: euler_complete_reachability_closed_cut_not_isolate_deletion · Uses: G001, S016 S018 · impliesBefore whole original carrier:original edge index=0;edge=[0, 1];from=0;new vertex=1 After original-edge path from0=[0, 1];reached=[0, 1] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S017 S019 · impliesBefore whole original carrier:original edge index=1;edge=[1, 2];from=1;new vertex=2 After original-edge path from0=[0, 1, 2];reached=[0, 1, 2] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S018 S020 · impliesBefore whole original carrier:original edge index=2;edge=[2, 3];from=2;new vertex=3 After original-edge path from0=[0, 1, 2, 3];reached=[0, 1, 2, 3] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S019 S021 · impliesBefore whole original carrier:original edge index=3;edge=[3, 4];from=3;new vertex=4 After original-edge path from0=[0, 1, 2, 3, 4];reached=[0, 1, 2, 3, 4] Conditions: none Give an actual-edge path for every discovered vertex.Start at the first actual support vertex rather than assuming vertex0 has an edge. Step identifiers and dependenciesRule: euler_connectivity_actual_path_witness · Uses: G001, S020 S022 · impliesBefore whole original carrier:complete permitted carrier=[0, 1, 2, 3, 4];reached=[0, 1, 2, 3, 4];unreached=[];ALL original edges=[[0, 1], [1, 2], [2, 3], [3, 4]] After no edge in carrier crosses reached/unreached cut;connected=Yes Conditions: none Exhausting BFS proves no edge crosses the cut,so an unreached vertex has no path from the start;otherwise path witnesses cover the carrier.Audit support and full carrier separately without silently deleting isolates to claim whole-graph connectivity. Step identifiers and dependenciesRule: euler_complete_reachability_closed_cut_not_isolate_deletion · Uses: G001, S021 S023 · impliesBefore complete degree list=[1, 2, 2, 2, 1];ALL odd vertices=[0, 4];actual nonisolated support=[0, 1, 2, 3, 4];support connected=Yes;whole graph connected=Yes After ANY full-edge trail joins all nonisolated vertices in one support component;each internal visit pairs incident edges,leaving only0 or2 odd endpoints Conditions: none Any all-edge trail puts every nonisolated vertex into its single walk component.Each internal entry/exit pairs incident edges;only distinct endpoints can leave one unmatched incidence,so there are0 or2 odd vertices.This is the universal necessity argument,not a guess from one tested walk.Isolates are outside edge support. Step identifiers and dependenciesRule: euler_necessary_connected_support_and_degree_parity · Uses: G001, S022 S024 · impliesBefore Hierholzer stack top=0;first unused incident ORIGINAL edge index=0;edge=[0, 1] After mark edge used ONCE;push vertex=1;current stack=[0, 1];used edge set=[0] Conditions: none Extend along an actual unused incident edge and mark it once.The finite used-edge count increases;vertices may recur but edges do not. Step identifiers and dependenciesRule: euler_constructive_unused_edge_extension · Uses: G001, S023 S025 · impliesBefore Hierholzer stack top=1;first unused incident ORIGINAL edge index=1;edge=[1, 2] After mark edge used ONCE;push vertex=2;current stack=[0, 1, 2];used edge set=[0, 1] Conditions: none Extend along an actual unused incident edge and mark it once.The finite used-edge count increases;vertices may recur but edges do not. Step identifiers and dependenciesRule: euler_constructive_unused_edge_extension · Uses: G001, S024 S026 · impliesBefore Hierholzer stack top=2;first unused incident ORIGINAL edge index=2;edge=[2, 3] After mark edge used ONCE;push vertex=3;current stack=[0, 1, 2, 3];used edge set=[0, 1, 2] Conditions: none Extend along an actual unused incident edge and mark it once.The finite used-edge count increases;vertices may recur but edges do not. Step identifiers and dependenciesRule: euler_constructive_unused_edge_extension · Uses: G001, S025 S027 · impliesBefore Hierholzer stack top=3;first unused incident ORIGINAL edge index=3;edge=[3, 4] After mark edge used ONCE;push vertex=4;current stack=[0, 1, 2, 3, 4];used edge set=[0, 1, 2, 3] Conditions: none Extend along an actual unused incident edge and mark it once.The finite used-edge count increases;vertices may recur but edges do not. Step identifiers and dependenciesRule: euler_constructive_unused_edge_extension · Uses: G001, S026 S028 · impliesBefore Hierholzer current stack=[0, 1, 2, 3, 4];top vertex has NO unused incident edge After finalize top into reverse output=[4];remaining stack=[0, 1, 2, 3] Conditions: none Backtrack and collect vertices in reverse only when no unused incident edge remains.This records the splicing of closed segments without traversing nonexistent edges. Step identifiers and dependenciesRule: euler_constructive_backtracking_cycle_splice · Uses: G001, S027 S029 · impliesBefore Hierholzer current stack=[0, 1, 2, 3];top vertex has NO unused incident edge After finalize top into reverse output=[4, 3];remaining stack=[0, 1, 2] Conditions: none Backtrack and collect vertices in reverse only when no unused incident edge remains.This records the splicing of closed segments without traversing nonexistent edges. Step identifiers and dependenciesRule: euler_constructive_backtracking_cycle_splice · Uses: G001, S028 S030 · impliesBefore Hierholzer current stack=[0, 1, 2];top vertex has NO unused incident edge After finalize top into reverse output=[4, 3, 2];remaining stack=[0, 1] Conditions: none Backtrack and collect vertices in reverse only when no unused incident edge remains.This records the splicing of closed segments without traversing nonexistent edges. Step identifiers and dependenciesRule: euler_constructive_backtracking_cycle_splice · Uses: G001, S029 S031 · impliesBefore Hierholzer current stack=[0, 1];top vertex has NO unused incident edge After finalize top into reverse output=[4, 3, 2, 1];remaining stack=[0] Conditions: none Backtrack and collect vertices in reverse only when no unused incident edge remains.This records the splicing of closed segments without traversing nonexistent edges. Step identifiers and dependenciesRule: euler_constructive_backtracking_cycle_splice · Uses: G001, S030 S032 · impliesBefore Hierholzer current stack=[0];top vertex has NO unused incident edge After finalize top into reverse output=[4, 3, 2, 1, 0];remaining stack=[] Conditions: none Backtrack and collect vertices in reverse only when no unused incident edge remains.This records the splicing of closed segments without traversing nonexistent edges. Step identifiers and dependenciesRule: euler_constructive_backtracking_cycle_splice · Uses: G001, S031 S033 · impliesBefore connected nonisolated support=[0, 1, 2, 3, 4];odd vertices=[0, 4];finished reversed construction After ACTUAL Euler witness walk=[0, 1, 2, 3, 4];actual ORIGINAL edge order=[0, 1, 2, 3];every original edge once;endpoints have required parity Conditions: none Map every step of the final walk back to original edges and verify length m+1,unique indices and complete coverage.This directly witnesses existence in this graph.With no odd vertices it closes;with two its endpoints are precisely those vertices.Parity alone is not the existence certificate,and no Hamiltonian property follows. Step identifiers and dependenciesRule: euler_sufficiency_actual_full_edge_witness_not_parity_alone · Uses: G001, S032 ## Reverse checks - S033 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S032 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S031 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S030 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S029 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S028 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S027 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S026 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S025 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S024 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S023 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S022 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S021 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S016 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S015 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - 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 — Recompute Euler vertex4 exact incident edge count with exact rational arithmetic, not rounded decimals. - 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 — Recompute Euler vertex3 exact incident edge count with exact rational arithmetic, not rounded decimals. - 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 — Recompute Euler vertex2 exact incident edge count with exact rational arithmetic, not rounded decimals. - 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 — Recompute Euler vertex1 exact incident edge count with exact rational arithmetic, not rounded decimals. - 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 — Recompute Euler vertex0 exact incident edge count with exact rational arithmetic, not rounded decimals. - 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 ([1, 2, 2, 2, 1], [0, 4], Yes, open_euler_trail, zero_or_two_odd_vertices_on_connected_edge_support) 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: fa1f2894133f8aab5a11c2156592570be32402fd7a6e160a1970e5df3fc286ef - candidate record SHA-256: 371fcdb4c71a964b092a7576309e687b2c0178c8823abdbf514f62f096301675 - semantic review receipt SHA-256: efee5462991619d6ed9f64f11ddb085e5614ef33f9f8fcd8cf29b9329f8fd301 - question-first witness SHA-256: acf91fa1622f01d2cf04b2c513294254323665351f660f2628aaafdb869c4ff2 - Lean: NOT_RUN · human review: NOT_PERFORMED [Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261014-advance-20261105-r04-eulerian-trail-0029.json)