# Question 16372: A Maximal Matching May Still Have Smaller Cardinality than Another Matching [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-0072) 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-16372 · q-20261014-advance-20261101-r05-graph-matching-0072 ## 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, 3], 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. Give (valid_matching?,addable_edge_indexes,maximal?,maximal_not_necessarily_maximum). List unselected original edges with both endpoints unmatched, in original index order. - 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, 3], 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. Give (valid_matching?,addable_edge_indexes,maximal?,maximal_not_necessarily_maximum). List unselected original edges with both endpoints unmatched, in original index order. ## 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, 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, 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 · calculationBefore matching edge3 endpoint2 incidence := sum(0, 1) After 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, S005 S007 · calculationBefore matching edge3 endpoint3 incidence := sum(0, 1) After 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, S006 S008 · impliesBefore 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, S007 S009 · impliesBefore 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, S008 S010 · impliesBefore original edge index=0;edge=[0, 1];already selected=Yes;endpoints both unmatched=No After directly addable original edge=No Conditions: none A direct extension must be an unselected original edge with both endpoints unmatched.It cannot replace selected edges.Testing every direct extension addresses maximality,not maximum cardinality. Step identifiers and dependenciesRule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S009 S011 · impliesBefore original edge index=1;edge=[0, 2];already selected=No;endpoints both unmatched=No After directly addable original edge=No Conditions: none A direct extension must be an unselected original edge with both endpoints unmatched.It cannot replace selected edges.Testing every direct extension addresses maximality,not maximum cardinality. Step identifiers and dependenciesRule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S010 S012 · impliesBefore original edge index=2;edge=[1, 2];already selected=No;endpoints both unmatched=No After directly addable original edge=No Conditions: none A direct extension must be an unselected original edge with both endpoints unmatched.It cannot replace selected edges.Testing every direct extension addresses maximality,not maximum cardinality. Step identifiers and dependenciesRule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S011 S013 · impliesBefore original edge index=3;edge=[2, 3];already selected=Yes;endpoints both unmatched=No After directly addable original edge=No Conditions: none A direct extension must be an unselected original edge with both endpoints unmatched.It cannot replace selected edges.Testing every direct extension addresses maximality,not maximum cardinality. Step identifiers and dependenciesRule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S012 S014 · impliesBefore original edge index=4;edge=[4, 5];already selected=No;endpoints both unmatched=Yes After directly addable original edge=Yes Conditions: none A direct extension must be an unselected original edge with both endpoints unmatched.It cannot replace selected edges.Testing every direct extension addresses maximality,not maximum cardinality. Step identifiers and dependenciesRule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S013 S015 · impliesBefore matching valid=Yes;all directly addable original indices=[4] After maximal=No;maximal_not_necessarily_maximum Conditions: none A valid matching with no direct extension is maximal.Replacing some edges may yield a larger matching,so maximality proves neither maximum size nor perfect coverage. Step identifiers and dependenciesRule: matching_maximal_not_maximum_or_perfect · 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 — 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 — Recompute matching edge3 endpoint3 incidence with exact rational arithmetic, not rounded decimals. - S006 · premise_and_result_audit — Recompute matching edge3 endpoint2 incidence with exact rational arithmetic, not rounded decimals. - 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 (Yes, [4], No, maximal_not_necessarily_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: 3dfae256872a11ca7da70da8447273e295a6e6e5e216e9c5d679a8dfc94890f2 - candidate record SHA-256: 7b0588e1ca5e92108ac28007b74cdca94a0d3f3bf7efa45677d881906fddfae4 - 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-0072.json)