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, 3], [2, 3]], 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, 3], [2, 3]], 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.
Step-by-step derivation
S001 · implies
Before
complete original carrier Fin(6);original edge list=[[0, 1], [0, 2], [1, 3], [2, 3]]
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 dependencies
Rule: matching_original_canonical_graph_not_silent_normalization · Uses: G001
S002 · implies
Before
matching:raw original-edge indices=[0, 3];original canonical edges=[[0, 1], [0, 2], [1, 3], [2, 3]]
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 dependencies
Rule: matching_selected_original_edge_indexes_not_new_edges · Uses: G001, S001
S003 · calculation
Before
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 dependencies
Rule: exact_rational_arithmetic · Uses: G001, S002
S004 · calculation
Before
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 dependencies
Rule: exact_rational_arithmetic · Uses: G001, S003
S005 · implies
Before
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 dependencies
Rule: matching_every_selected_edge_endpoint_incidence · Uses: G001, S004
S006 · calculation
Before
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 dependencies
Rule: exact_rational_arithmetic · Uses: G001, S005
S007 · calculation
Before
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 dependencies
Rule: exact_rational_arithmetic · Uses: G001, S006
S008 · implies
Before
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 dependencies
Rule: matching_every_selected_edge_endpoint_incidence · Uses: G001, S007
S009 · implies
Before
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 dependencies
Rule: matching_validity_separate_from_coverage_or_optimality · Uses: G001, S008
S010 · implies
Before
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 dependencies
Rule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S009
S011 · implies
Before
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 dependencies
Rule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S010
S012 · implies
Before
original edge index=2;edge=[1, 3];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 dependencies
Rule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S011
S013 · implies
Before
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 dependencies
Rule: matching_every_unselected_edge_direct_extension_test · Uses: G001, S012
S014 · implies
Before
matching valid=Yes;all directly addable original indices=[]
After
maximal=Yes;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 dependencies
Rule: matching_maximal_not_maximum_or_perfect · Uses: G001, S013