Question 26052: A Cover Can Resist Every Single Deletion yet Be Larger than Another Cover

On this page

Original question and givens
Definition and scope
Step-by-step derivation
Reverse checks
Result
This question review and source binding

← Question derivation index · Original question batch

R0051-26052 · q-20261015-advance-20261115-r06-minimum-vertex-cover-0052

Original question and givens

Use complete unique vertices=[c0, l0_0, l0_1, l0_2] and loop-free duplicate-free undirected edges=[[c0, l0_0], [c0, l0_1], [c0, l0_2]], candidate cover=[l0_0, l0_1, l0_2]. An edge needs at least one selected endpoint. Preserve source canonical subset order. Give (candidate, deletion_rows, inclusion_minimal, minimum_size, smaller_cover, minimum, certificate).

G001 — Use complete unique vertices=[c0, l0_0, l0_1, l0_2] and loop-free duplicate-free undirected edges=[[c0, l0_0], [c0, l0_1], [c0, l0_2]], candidate cover=[l0_0, l0_1, l0_2]. An edge needs at least one selected endpoint. Preserve source canonical subset order. Give (candidate, deletion_rows, inclusion_minimal, minimum_size, smaller_cover, minimum, certificate).

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-minimum-vertex-cover

Step-by-step derivation

S001 · implies

Before

source roles = [mincover-minimal-not-minimum]

After

derived = [[candidate, deletion_rows, inclusion_minimal, minimum_size, smaller_cover, minimum, certificate]]

Conditions: none

List the full source field order without JavaScript.Original modes select contract6/4/6/6 and IVT8/7/8 roles,without padding or answer-shape inference.

Step identifiers and dependencies

Rule: source_ordered_fields_without_JS · Uses: G001

S002 · implies

Before

source roles = [[c0, l0_0, l0_1, l0_2], [[c0, l0_0], [c0, l0_1], [c0, l0_2]], [l0_0, l0_1, l0_2]]

After

derived = [[c0, l0_0, l0_1, l0_2], [[c0, l0_0], [c0, l0_1], [c0, l0_2]], [l0_0, l0_1, l0_2]]

Conditions: none

The carrier is nonempty with at most12 vertices;sort endpoints by UTF16 then edge families in English.Reject loops/reversed duplicates.An omitted candidate stays null,not an invented empty candidate.

Step identifiers and dependencies

Rule: Mincover_complete_simple_graph_UTF16_English_and_optional_candidate · Uses: G001, S001

S003 · implies

Before

source roles = [[c0, l0_0, l0_1, l0_2], [[c0, l0_0], [c0, l0_1], [c0, l0_2]], 16]

After

derived = [[1, 3, 5, 7, 9, 11, 13, 14, 15], [[0, 0], [2, 1], [4, 0], [6, 2], [8, 0], [10, 1], [12, 0]], [[c0], [c0, l0_0], [c0, l0_1], [c0, l0_0, l0_1], [c0, l0_2], [c0, l0_0, l0_2], [c0, l0_1, l0_2], [l0_0, l0_1, l0_2], [c0, l0_0, l0_1, l0_2]], [0, 1, 3, 4, 1], 1, [[c0]]]

Conditions: none

Audit every mask against every edge,retaining the first uncovered-edge refutation for each failure and every accepted set in source order.Zero smaller-size counts give a lower bound and actual minimum covers attain it.Keep all ties in numeric-mask order,not English/size order.

Step identifiers and dependencies

Rule: Mincover_ALL_masks_acceptance_refutations_ALLcovers_ALLminimizers · Uses: G001, S002

S004 · implies

Before

source roles = [[l0_0, l0_1, l0_2], [[c0, l0_0], [c0, l0_1], [c0, l0_2]]]

After

derived = [[[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes]], 3, 1, [c0]]

Conditions: none

First qualify an actual candidate cover.The smaller witness is the first minimum from the complete source list,not an arbitrary small set.

Step identifiers and dependencies

Rule: Mincover_actual_candidate_complete_cover_and_smaller_witness · Uses: G001, S003

S005 · implies

Before

source roles = [[l0_0, l0_1, l0_2], [[l0_0, [l0_1, l0_2], No], [l0_1, [l0_0, l0_2], No], [l0_2, [l0_0, l0_1], No]]]

After

derived = [Yes, 1, [c0], No]

Conditions: none

Every single deletion loses coverage,so the candidate is inclusion-minimal.But exhaustive search supplies a strictly smaller cover,so it is not minimum.Superset monotonicity makes deletion tests cover all proper-subset obligations,not maximum or optimal size.

Step identifiers and dependencies

Rule: Mincover_ALL_single_deletions_minimal_BUT_smaller_cover_exists · Uses: G001, S004

Reverse checks

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 — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S003 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
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

([l0_0, l0_1, l0_2], [[l0_0, [l0_1, l0_2], No], [l0_1, [l0_0, l0_2], No], [l0_2, [l0_0, l0_1], No]], Yes, 1, [c0], No, inclusion_minimal_is_not_minimum)

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: a7a673d2841f5254802ef87ee8794ef8aab8d44c79c3e321bc6346434e29e49f
candidate record SHA-256: 56c737ca053d3451fb6a0dfcb3783206a441d3bbc09df2c71d9ad5633fe62855
semantic review receipt SHA-256: 90df1e889242e9afdf01e068788ee8500ef366ffcfc0496e30a6800de32631c3
question-first witness SHA-256: ae1e849608590ca856c9f3b6911ba58e3bf53c608eb7369606192a770f48bd5c
Lean: NOT_RUN · human review: NOT_PERFORMED

Same-source full JSON