Skip to content

Erdős Problem #715

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

Berge (or Berge–Sauer) asked whether every finite 4-regular graph contains a 3-regular subgraph; Erdős also asked whether some fixed regular degree r suffices. The maintained source marks the 4-regular question PROVED, attributing the affirmative result to Tashkinov 1982. The subgraph is not assumed induced or spanning; adding either requirement changes the statement.

A small example

The complete graph K_5 is 4-regular. On any chosen four vertices its K_4 subgraph is 3-regular, giving a positive finite example. The bipartite graph K_{4,4} is 4-regular; deleting one perfect matching yields a spanning 3-regular subgraph. Neither verifies the universal theorem.

What is known

Tashkinov [Ta82] answered the degree-4 case affirmatively. Alon–Friedland–Kalai [AFK84] proved that any 4-regular graph augmented by a single edge contains a cubic (3-regular) subgraph; the source derives every r-regular graph with r≥5 contains a cubic subgraph. The stronger family of results must retain simple-graph versus multigraph assumptions. Published theorem attributions come from maintained #715 (edited 2025-10-06); original Tashkinov Russian-language proof and AFK publication were not directly read.

GCL's current state

The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.

Critical source-scope distinction: Tashkinov 4-regular cubic subgraph noninduced; Alon–Friedland–Kalai related r>=5 result.

What remains

ERDOS-715-CUBIC-SUBGRAPH-SOURCE. Retrieve Tashkinov 1982 proof and verify simple finite graph, parity, connectedness and nonspanning assumptions. Construct exact K5 and K4,4 subgraph certificates and use a finite n graph search to test one candidate general lemma, not general theorem.

Sources and claim boundaries

Maintained source #715 · GCL issue report. Full original mathematical arguments not independently replayed; The full original mathematical arguments are not independently replayed.

Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1986 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction