# Question 16397: A Supplied Larger Valid Matching Refutes Maximum Cardinality [Return to catalogue page 82](https://ocme.evemisslab.com/en/questions/page/82/) [← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261014-advance-20261101-r05-graph-matching-foundations/#q-20261014-advance-20261101-r05-graph-matching-0097) 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. R0031-16397 · q-20261014-advance-20261101-r05-graph-matching-0097 ## Original question and givens Use the complete finite undirected loop-free simple graph on Fin(6)={0,…,5} with canonical edges=[[0, 1], [0, 2], [1, 2], [2, 3], [4, 5]], endpoints increasing and the edge list lexicographically sorted. The source rejects noncanonical or duplicate edges. Select original edge indexes matching=[0], sorted increasingly with duplicates forbidden. A matching has pairwise disjoint endpoints; the empty matching is allowed. Keep matching validity, maximality, maximum cardinality and perfect coverage distinct. Compare larger_matching=[0, 3], also normalized as distinct original edge indexes. Give (matching_indexes,larger_indexes,size,larger_size,witness?,conclusion). The conclusion is supplied_matching_not_maximum or no_maximum_conclusion. - G001 — Use the complete finite undirected loop-free simple graph on Fin(6)={0,…,5} with canonical edges=[[0, 1], [0, 2], [1, 2], [2, 3], [4, 5]], endpoints increasing and the edge list lexicographically sorted. The source rejects noncanonical or duplicate edges. Select original edge indexes matching=[0], sorted increasingly with duplicates forbidden. A matching has pairwise disjoint endpoints; the empty matching is allowed. Keep matching validity, maximality, maximum cardinality and perfect coverage distinct. Compare larger_matching=[0, 3], also normalized as distinct original edge indexes. Give (matching_indexes,larger_indexes,size,larger_size,witness?,conclusion). The conclusion is supplied_matching_not_maximum or no_maximum_conclusion. ## 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-graph-matching](https://ocme.evemisslab.com/en/mko/mko-graph-matching/) ## Step-by-step derivation S001 · impliesBefore complete original carrier Fin(6);original edge list=[[0, 1], [0, 2], [1, 2], [2, 3], [4, 5]] After input ALREADY has increasing endpoints and lexicographic edge order;loop-free unique edges=Yes;whole carrier=[0, 1, 2, 3, 4, 5] Conditions: none This family requires an already canonical input,not silent normalization of unsorted or reversed duplicate edges.Do not reuse the previous round's normalization guard.Edge indices bind to this original graph,and the complete carrier retains isolates. Step identifiers and dependenciesRule: matching_original_canonical_graph_not_silent_normalization · Uses: G001 S002 · impliesBefore matching:raw original-edge indices=[0];original canonical edges=[[0, 1], [0, 2], [1, 2], [2, 3], [4, 5]] After sorted duplicate-free selected indices=[0];selected edges=[[0, 1]] Conditions: none Sort the selected indices but reject duplicates and select only original edges.The empty matching is allowed.Do not invent edges from endpoint sets or confuse edge indices with vertex labels. Step identifiers and dependenciesRule: matching_selected_original_edge_indexes_not_new_edges · Uses: G001, S001 S003 · calculationBefore matching edge0 endpoint0 incidence := sum(0, 1) After matching edge0 endpoint0 incidence = 1 Conditions: none Compute exactly from original field roles and established intermediates,retaining denominators,signs,indices and the complete carrier. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S002 S004 · calculationBefore matching edge0 endpoint1 incidence := sum(0, 1) After matching edge0 endpoint1 incidence = 1 Conditions: none Compute exactly from original field roles and established intermediates,retaining denominators,signs,indices and the complete carrier. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S003 S005 · impliesBefore matching:selected original edge index=0;edge=[0, 1] After cumulative endpoint counts in first-seen order=[[0, 1], [1, 1]] Conditions: none Increment both endpoints of each selected edge.A count above1 is an endpoint conflict.Keep first-seen endpoint order instead of inventing a numerical sort for the conflict output. Step identifiers and dependenciesRule: matching_every_selected_edge_endpoint_incidence · Uses: G001, S004 S006 · impliesBefore matching:final first-seen endpoint counts=[[0, 1], [1, 1]] After conflicting vertices first-seen=[];matched vertices sorted=[0, 1];matching valid=Yes Conditions: none Pairwise disjoint endpoints define a matching.An invalid selection may still cover many vertices.Coverage does not replace validity or prove maximality,maximum size or perfectness. Step identifiers and dependenciesRule: matching_validity_separate_from_coverage_or_optimality · Uses: G001, S005 S007 · impliesBefore larger_matching:raw original-edge indices=[0, 3];original canonical edges=[[0, 1], [0, 2], [1, 2], [2, 3], [4, 5]] After sorted duplicate-free selected indices=[0, 3];selected edges=[[0, 1], [2, 3]] Conditions: none Sort the selected indices but reject duplicates and select only original edges.The empty matching is allowed.Do not invent edges from endpoint sets or confuse edge indices with vertex labels. Step identifiers and dependenciesRule: matching_selected_original_edge_indexes_not_new_edges · Uses: G001, S006 S008 · calculationBefore larger_matching edge0 endpoint0 incidence := sum(0, 1) After larger_matching edge0 endpoint0 incidence = 1 Conditions: none Compute exactly from original field roles and established intermediates,retaining denominators,signs,indices and the complete carrier. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S007 S009 · calculationBefore larger_matching edge0 endpoint1 incidence := sum(0, 1) After larger_matching edge0 endpoint1 incidence = 1 Conditions: none Compute exactly from original field roles and established intermediates,retaining denominators,signs,indices and the complete carrier. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S008 S010 · impliesBefore larger_matching:selected original edge index=0;edge=[0, 1] After cumulative endpoint counts in first-seen order=[[0, 1], [1, 1]] Conditions: none Increment both endpoints of each selected edge.A count above1 is an endpoint conflict.Keep first-seen endpoint order instead of inventing a numerical sort for the conflict output. Step identifiers and dependenciesRule: matching_every_selected_edge_endpoint_incidence · Uses: G001, S009 S011 · calculationBefore larger_matching edge3 endpoint2 incidence := sum(0, 1) After larger_matching edge3 endpoint2 incidence = 1 Conditions: none Compute exactly from original field roles and established intermediates,retaining denominators,signs,indices and the complete carrier. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S010 S012 · calculationBefore larger_matching edge3 endpoint3 incidence := sum(0, 1) After larger_matching edge3 endpoint3 incidence = 1 Conditions: none Compute exactly from original field roles and established intermediates,retaining denominators,signs,indices and the complete carrier. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S011 S013 · impliesBefore larger_matching:selected original edge index=3;edge=[2, 3] After cumulative endpoint counts in first-seen order=[[0, 1], [1, 1], [2, 1], [3, 1]] Conditions: none Increment both endpoints of each selected edge.A count above1 is an endpoint conflict.Keep first-seen endpoint order instead of inventing a numerical sort for the conflict output. Step identifiers and dependenciesRule: matching_every_selected_edge_endpoint_incidence · Uses: G001, S012 S014 · impliesBefore larger_matching:final first-seen endpoint counts=[[0, 1], [1, 1], [2, 1], [3, 1]] After conflicting vertices first-seen=[];matched vertices sorted=[0, 1, 2, 3];matching valid=Yes Conditions: none Pairwise disjoint endpoints define a matching.An invalid selection may still cover many vertices.Coverage does not replace validity or prove maximality,maximum size or perfectness. Step identifiers and dependenciesRule: matching_validity_separate_from_coverage_or_optimality · Uses: G001, S013 S015 · impliesBefore first selection valid=Yes;comparison selection valid=Yes;original sizes=[1, 2] After strictly larger valid witness=Yes;conclusion=supplied_matching_not_maximum Conditions: none Validate both selections and require strictly more edges in the second to refute maximum size of the first.Without such a witness,this comparison is inconclusive,not a proof that the first is maximum or perfect. Step identifiers and dependenciesRule: matching_larger_valid_witness_not_failed_comparison_optimality · Uses: G001, S014 ## Reverse checks - 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 — Recompute larger_matching edge3 endpoint3 incidence with exact rational arithmetic, not rounded decimals. - S011 · premise_and_result_audit — Recompute larger_matching edge3 endpoint2 incidence 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 larger_matching edge0 endpoint1 incidence with exact rational arithmetic, not rounded decimals. - S008 · premise_and_result_audit — Recompute larger_matching edge0 endpoint0 incidence with exact rational arithmetic, not rounded decimals. - 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 — Recompute matching edge0 endpoint1 incidence with exact rational arithmetic, not rounded decimals. - S003 · premise_and_result_audit — Recompute matching edge0 endpoint0 incidence 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 ([0], [0, 3], 1, 2, Yes, supplied_matching_not_maximum) 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: e46e1c462f231651c49ad9104c7f9bf4bf74704c2d00aaaaaca8bdd9b68fe1a4 - candidate record SHA-256: 51a77fd9013c1249e3b1ba21b9432af2080f158f5ff78a2d6a45fdb000f734bd - semantic review receipt SHA-256: 55bb21783e2125ecf1e67e42f83fd25bec0ccd493f911f4bb937a5e9d6f9369a - question-first witness SHA-256: 754ddf2a6039c5ef4aae78a538c6e9a1e9a58d4825aee194e869a27b8a4c95bb - Lean: NOT_RUN · human review: NOT_PERFORMED [Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261014-advance-20261101-r05-graph-matching-0097.json)