Question 16380: A Supplied Larger Valid Matching Refutes Maximum Cardinality

Original question and givens

Use the complete finite undirected loop-free simple graph on Fin(6)={0,…,5} with canonical edges=[[0, 1], [1, 2], [2, 3]], 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, 2], 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], [1, 2], [2, 3]], 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, 2], 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

Step-by-step derivation

complete original carrier Fin(6);original edge list=[[0, 1], [1, 2], [2, 3]]

input ALREADY has increasing endpoints and lexicographic edge order;loop-free unique edges=Yes;whole carrier=[0, 1, 2, 3, 4, 5]

matching:raw original-edge indices=[0];original canonical edges=[[0, 1], [1, 2], [2, 3]]

sorted duplicate-free selected indices=[0];selected edges=[[0, 1]]

matching edge0 endpoint0 incidence := sum(0, 1)

matching edge0 endpoint0 incidence = 1

matching edge0 endpoint1 incidence := sum(0, 1)

matching edge0 endpoint1 incidence = 1

matching:selected original edge index=0;edge=[0, 1]

cumulative endpoint counts in first-seen order=[[0, 1], [1, 1]]

matching:final first-seen endpoint counts=[[0, 1], [1, 1]]

conflicting vertices first-seen=[];matched vertices sorted=[0, 1];matching valid=Yes

larger_matching:raw original-edge indices=[0, 2];original canonical edges=[[0, 1], [1, 2], [2, 3]]

sorted duplicate-free selected indices=[0, 2];selected edges=[[0, 1], [2, 3]]

larger_matching edge0 endpoint0 incidence := sum(0, 1)

larger_matching edge0 endpoint0 incidence = 1

larger_matching edge0 endpoint1 incidence := sum(0, 1)

larger_matching edge0 endpoint1 incidence = 1

larger_matching:selected original edge index=0;edge=[0, 1]

cumulative endpoint counts in first-seen order=[[0, 1], [1, 1]]

larger_matching edge2 endpoint2 incidence := sum(0, 1)

larger_matching edge2 endpoint2 incidence = 1

larger_matching edge2 endpoint3 incidence := sum(0, 1)

larger_matching edge2 endpoint3 incidence = 1

larger_matching:selected original edge index=2;edge=[2, 3]

cumulative endpoint counts in first-seen order=[[0, 1], [1, 1], [2, 1], [3, 1]]

larger_matching:final first-seen endpoint counts=[[0, 1], [1, 1], [2, 1], [3, 1]]

conflicting vertices first-seen=[];matched vertices sorted=[0, 1, 2, 3];matching valid=Yes

first selection valid=Yes;comparison selection valid=Yes;original sizes=[1, 2]

strictly larger valid witness=Yes;conclusion=supplied_matching_not_maximum

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 edge2 endpoint3 incidence with exact rational arithmetic, not rounded decimals.
• S011 · premise_and_result_audit — Recompute larger_matching edge2 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, 2], 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.