Explore related knowledge and questions →
← Question derivation index · Original question batch
R0049-25440 · q-20261015-advance-20261114-r07-vertex-cover-0065
Use complete finite unique vertices=[v0, v1, v2, v3, v4, v5, v6], loop-free simple undirected edges=[[v0, v1], [v0, v2], [v0, v3], [v0, v4], [v0, v5]] and unique candidate subset=[v0, v1, v2, v3, v4, v5]. 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. Given superset=[v0, v1, v2, v3, v4, v5, v6], possibly equal to the candidate. Give (edgeless_graph, empty_cover_valid_if_edgeless_or_null, isolated_vertices, candidate, candidate_cover, superset, superset_cover, certificate).
G001 — Use complete finite unique vertices=[v0, v1, v2, v3, v4, v5, v6], loop-free simple undirected edges=[[v0, v1], [v0, v2], [v0, v3], [v0, v4], [v0, v5]] and unique candidate subset=[v0, v1, v2, v3, v4, v5]. 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. Given superset=[v0, v1, v2, v3, v4, v5, v6], possibly equal to the candidate. Give (edgeless_graph, empty_cover_valid_if_edgeless_or_null, isolated_vertices, candidate, candidate_cover, superset, superset_cover, certificate).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.
Before
source roles = [vcover-empty-isolated-superset]
After
derived = [[edgeless_graph, empty_cover_valid_if_edgeless_or_null, isolated_vertices, candidate, candidate_cover, superset, superset_cover, 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.
Rule: source_ordered_fields_without_JS · Uses: G001
Before
source roles = [[v0, v1, v2, v3, v4, v5, v6], [[v0, v1], [v0, v2], [v0, v3], [v0, v4], [v0, v5]], [v0, v1, v2, v3, v4, v5]]
After
derived = [[v0, v1, v2, v3, v4, v5, v6], [[v0, v1], [v0, v2], [v0, v3], [v0, v4], [v0, v5]], [v0, v1, v2, v3, v4, v5]]
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.
Rule: Vcover_complete_simple_undirected_graph_UTF16_then_English_order · Uses: G001, S001
Before
source roles = [0, [v0, v1], [v0, v1, v2, v3, v4, v5]]
After
derived = [[Yes, Yes], Yes]
Conditions: none
This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.
Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S002
Before
source roles = [1, [v0, v2], [v0, v1, v2, v3, v4, v5]]
After
derived = [[Yes, Yes], Yes]
Conditions: none
This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.
Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S003
Before
source roles = [2, [v0, v3], [v0, v1, v2, v3, v4, v5]]
After
derived = [[Yes, Yes], Yes]
Conditions: none
This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.
Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S004
Before
source roles = [3, [v0, v4], [v0, v1, v2, v3, v4, v5]]
After
derived = [[Yes, Yes], Yes]
Conditions: none
This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.
Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S005
Before
source roles = [4, [v0, v5], [v0, v1, v2, v3, v4, v5]]
After
derived = [[Yes, Yes], Yes]
Conditions: none
This edge is covered iff at least one endpoint is selected.Check the entire edge table,not vertex count.
Rule: Vcover_EVERY_edge_selected_endpoint_disjunction · Uses: G001, S006
Before
source roles = [[[[v0, v1], Yes], [[v0, v2], Yes], [[v0, v3], Yes], [[v0, v4], Yes], [[v0, v5], Yes]]]
After
derived = [Yes, null, [v6]]
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.
Rule: Vcover_COMPLETE_edge_conjunction_FIRST_uncovered_or_NULL · Uses: G001, S007
Before
source roles = [[[v0, v1], [v0, v2], [v0, v3], [v0, v4], [v0, v5]], [v6], [v0, v1, v2, v3, v4, v5], [v0, v1, v2, v3, v4, v5, v6]]
After
derived = [No, null, Yes]
Conditions: none
An edgeless graph permits the empty cover;otherwise this conditional field is null.If C covers and C is a subset of S,each selected endpoint remains in S,so S also covers.Equal supersets are allowed.
Rule: Vcover_empty_graph_conditional_NULL_and_cover_superset_monotonicity · Uses: G001, S008
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.(No, null, [v6], [v0, v1, v2, v3, v4, v5], Yes, [v0, v1, v2, v3, v4, v5, v6], Yes, empty_edge_graph_empty_cover_is_valid_isolated_vertices_are_optional_and_cover_supersets_remain_covers)
The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.
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.
input commit: 0f7be61e2c22317a4075561dc822c87d881a50dboriginal question SHA-256: f71b26871580ae6e3f509b5f00fae524c4b9c898e64251453db87e2c5ffffb6ecandidate record SHA-256: 3cd4e63adaa1f40922e38e0ab687cd23abcb85b693e677cc3d58db098590d237semantic review receipt SHA-256: 6212b8b0b3b273f3a514e26ebd17d7e81219c56a8f47e40047ee2b6bf01d1ba3question-first witness SHA-256: f32a23d5e1b66c7794c60def58741bcdfacff24f3cdfc9bc48109c8f71543cf3Lean: NOT_RUN · human review: NOT_PERFORMED