OCMEBilingual mathematics & derivations繁體中文

Explore related knowledge and questions →

Question 25457: 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-25457 · q-20261015-advance-20261114-r07-vertex-cover-0082

Original question and givens

Use complete finite unique vertices=[c0, l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], loop-free simple undirected edges=[[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7]] and unique candidate subset=[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]. 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, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], loop-free simple undirected edges=[[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7]] and unique candidate subset=[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]. 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, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7]], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[c0, l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7]], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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 = [2, [c0, l0_2], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, S004

S006 · implies

Before

source roles = [3, [c0, l0_3], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, S005

S007 · implies

Before

source roles = [4, [c0, l0_4], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, S006

S008 · implies

Before

source roles = [5, [c0, l0_5], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, S007

S009 · implies

Before

source roles = [6, [c0, l0_6], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, S008

S010 · implies

Before

source roles = [7, [c0, l0_7], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

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, S009

S011 · implies

Before

source roles = [[[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S010

S012 · implies

Before

source roles = [l0_0, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[[c0, l0_0], No], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S011

S013 · implies

Before

source roles = [l0_1, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[[c0, l0_0], Yes], [[c0, l0_1], No], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S012

S014 · implies

Before

source roles = [l0_2, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_1, l0_3, l0_4, l0_5, l0_6, l0_7], [[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], No], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S013

S015 · implies

Before

source roles = [l0_3, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_1, l0_2, l0_4, l0_5, l0_6, l0_7], [[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], No], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S014

S016 · implies

Before

source roles = [l0_4, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_1, l0_2, l0_3, l0_5, l0_6, l0_7], [[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], No], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S015

S017 · implies

Before

source roles = [l0_5, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_6, l0_7], [[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], No], [[c0, l0_6], Yes], [[c0, l0_7], 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, S016

S018 · implies

Before

source roles = [l0_6, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_7], [[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], No], [[c0, l0_7], 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, S017

S019 · implies

Before

source roles = [l0_7, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7]]

After

derived = [[l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6], [[[c0, l0_0], Yes], [[c0, l0_1], Yes], [[c0, l0_2], Yes], [[c0, l0_3], Yes], [[c0, l0_4], Yes], [[c0, l0_5], Yes], [[c0, l0_6], Yes], [[c0, l0_7], 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, S018

S020 · implies

Before

source roles = [[c0, l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[c0, l0_0], [c0, l0_1], [c0, l0_2], [c0, l0_3], [c0, l0_4], [c0, l0_5], [c0, l0_6], [c0, l0_7]], [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[l0_0, [l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], No], [l0_1, [l0_0, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], No], [l0_2, [l0_0, l0_1, l0_3, l0_4, l0_5, l0_6, l0_7], No], [l0_3, [l0_0, l0_1, l0_2, l0_4, l0_5, l0_6, l0_7], No], [l0_4, [l0_0, l0_1, l0_2, l0_3, l0_5, l0_6, l0_7], No], [l0_5, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_6, l0_7], No], [l0_6, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_7], No], [l0_7, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6], No]]]

After

derived = [512, [0, 1, 8, 28, 56, 70, 56, 28, 9, 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, S019

Reverse checks

  • S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • S016 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
  • 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 — 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_2, l0_3, l0_4, l0_5, l0_6, l0_7], [[l0_0, [l0_1, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], No], [l0_1, [l0_0, l0_2, l0_3, l0_4, l0_5, l0_6, l0_7], No], [l0_2, [l0_0, l0_1, l0_3, l0_4, l0_5, l0_6, l0_7], No], [l0_3, [l0_0, l0_1, l0_2, l0_4, l0_5, l0_6, l0_7], No], [l0_4, [l0_0, l0_1, l0_2, l0_3, l0_5, l0_6, l0_7], No], [l0_5, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_6, l0_7], No], [l0_6, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_7], No], [l0_7, [l0_0, l0_1, l0_2, l0_3, l0_4, l0_5, l0_6], 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: 9de879dae0a1f7653ba9f7695626498c48467befaf5b4dd4941bea9a935eefe2
  • candidate record SHA-256: e213b7b10ec02b1a7ff23973b4c3992389f65a578487ecf80409cff94b11f026
  • semantic review receipt SHA-256: 6212b8b0b3b273f3a514e26ebd17d7e81219c56a8f47e40047ee2b6bf01d1ba3
  • question-first witness SHA-256: f32a23d5e1b66c7794c60def58741bcdfacff24f3cdfc9bc48109c8f71543cf3
  • Lean: NOT_RUN · human review: NOT_PERFORMED
Same-source full JSON