OCMEBilingual mathematics & derivations繁體中文

Explore related knowledge and questions →

Question 25451: Inclusion-Minimal Covers Need Not Have Minimum Cardinality

On this page
  1. Original question and givens
  2. Definition and scope
  3. Step-by-step derivation
  4. Reverse checks
  5. Result
  6. This question review and source binding

Return to catalogue page 128

← Question derivation index · Original question batch

R0049-25451 · q-20261015-advance-20261114-r07-vertex-cover-0076

Original question and givens

Use complete finite unique vertices=[c0, l0_0, l0_1], loop-free simple undirected edges=[[c0, l0_0], [c0, l0_1]] and unique candidate subset=[l0_0, l0_1]. Edges normalize to sorted unordered pairs and are duplicate-free. A cover selects at least one endpoint of every edge; isolated vertices need not be selected. Give (candidate, deletion_rows, inclusion_minimal, minimum_size, minimum, minimality_tests_agree, certificate).

  • G001 — Use complete finite unique vertices=[c0, l0_0, l0_1], loop-free simple undirected edges=[[c0, l0_0], [c0, l0_1]] and unique candidate subset=[l0_0, l0_1]. Edges normalize to sorted unordered pairs and are duplicate-free. A cover selects at least one endpoint of every edge; isolated vertices need not be selected. Give (candidate, deletion_rows, inclusion_minimal, minimum_size, minimum, minimality_tests_agree, 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.

Step-by-step derivation

S001 · implies

Before

source roles = [vcover-minimal-vs-minimum-boundary]

After

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

Conditions: none

List the full source field order without JavaScript.LP boundary modes all have6 fields but select different roles from the original mode,not answer shape.

Step identifiers and dependencies

Rule: source_ordered_fields_without_JS · Uses: G001

S002 · implies

Before

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

After

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

Conditions: none

The carrier is nonempty with at most12 vertices.Normalize endpoints by JS UTF16<,then source English canonical edge order.Reject loops/reversed duplicate edges;this is not a directed graph or edge cover.

Step identifiers and dependencies

Rule: Vcover_complete_simple_undirected_graph_UTF16_then_English_order · Uses: G001, S001

S003 · implies

Before

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

After

derived = [[No, Yes], Yes]

Conditions: none

This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.

Step identifiers and dependencies

Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S002

S004 · implies

Before

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

After

derived = [[No, Yes], Yes]

Conditions: none

This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.

Step identifiers and dependencies

Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S003

S005 · implies

Before

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

After

derived = [Yes, null, []]

Conditions: none

Conjoin all edges and retain the first uncovered edge in source order,or null,notFalse.Isolated vertices have no incident coverage obligation and are optional.

Step identifiers and dependencies

Rule: Vcover_COMPLETE_edge_conjunction_FIRST_uncovered_or_NULL · Uses: G001, S004

S006 · implies

Before

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

After

derived = [[l0_1], [[[c0, l0_0], No], [[c0, l0_1], Yes]], No]

Conditions: none

Delete only this vertex and recheck every edge,without reusing another deletion result.

Step identifiers and dependencies

Rule: Vcover_EACH_single_vertex_deletion_complete_edge_test · Uses: G001, S005

S007 · implies

Before

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

After

derived = [[l0_0], [[[c0, l0_0], Yes], [[c0, l0_1], No]], No]

Conditions: none

Delete only this vertex and recheck every edge,without reusing another deletion result.

Step identifiers and dependencies

Rule: Vcover_EACH_single_vertex_deletion_complete_edge_test · Uses: G001, S006

S008 · implies

Before

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

After

derived = [8, [0, 1, 3, 1], [1, [c0]], Yes, 1, No, No]

Conditions: none

Count covers by size over all2^n subsets.Zero counts at smaller sizes give a lower bound and the explicit witness attains it.By superset monotonicity,any proper-subset cover would make some single deletion a cover,so deletion tests characterize inclusion-minimality,not minimum cardinality.The last flag compares two Booleans;bothFalse may agree.

Step identifiers and dependencies

Rule: Vcover_ALL_subsets_cardinality_counts_minimum_witness_and_GENERAL_minimality · Uses: G001, S007

Reverse checks

  • 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 — 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 — 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_0, [l0_1], No], [l0_1, [l0_0], No]], Yes, 1, No, No, inclusion_minimal_means_no_single_deletion_while_minimum_compares_all_covers)

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: df4976552378d451d0b5cabedc510bd5e545d5e5445925afa27dc22c6ad905b8
  • candidate record SHA-256: baa953764c1d7ed161f8e7e22349d465a1e47eb36892e624a1a9470583bf62fc
  • semantic review receipt SHA-256: 6212b8b0b3b273f3a514e26ebd17d7e81219c56a8f47e40047ee2b6bf01d1ba3
  • question-first witness SHA-256: f32a23d5e1b66c7794c60def58741bcdfacff24f3cdfc9bc48109c8f71543cf3
  • Lean: NOT_RUN · human review: NOT_PERFORMED
Same-source full JSON