leanprover-community / leanprover-community/mathlib4
Graph theory def: Minimal/minimum vertex covers
Nobody has claimed this yet.
- Dominant language
- Lean
- Stars
- 4.2k
- Forks
- 1.7k
- PR merge metrics
- No merged PRs in 30d
Description
Vertex covers for simple graphs exist as SimpleGraph.IsVertexCover.
I suggest we're missing the following definitions:
open Cardinal
def IsMinimalCover (G : SimpleGraph V) (c : Set V) :=
Minimal G.IsVertexCover c
def IsMinimumCover (G : SimpleGraph V) (c : Set V) :=
MinimalFor G.IsVertexCover (#·) c
and basic API for them, e.g. G.IsMinimalCover c → ∀ v ∈ c, ¬G.IsIsolated v, since any isolated vertices can be removed to create a smaller cover.
An important lemma is c.Finite → G.IsMinimumCover c → G.IsMinimalCover c. This comment might help as it's a similar situation.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with SimpleGraph.IsVertexCover in Mathlib/Combinatorics/SimpleGraph/VertexCover.html and review the linked discussion from pull request 32555. Add the minimal and minimum vertex-cover definitions, basic API such as the isolated-vertex result, and establish the finite minimum-to-minimal implication.】【。
Written by the indexing model from the issue text.
Assessment
- Domain
- devtools
- Issue type
- Feature
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100