Skip to content

[Merged by Bors] - feat(Combinatorics/SimpleGraph): isolated vertices#34808

Closed
YaelDillies wants to merge 5 commits intoleanprover-community:masterfrom
YaelDillies:simple_graph_isolated
Closed

[Merged by Bors] - feat(Combinatorics/SimpleGraph): isolated vertices#34808
YaelDillies wants to merge 5 commits intoleanprover-community:masterfrom
YaelDillies:simple_graph_isolated

Conversation

@YaelDillies
Copy link
Copy Markdown
Contributor

@YaelDillies YaelDillies commented Feb 3, 2026

From ProofBench


Open in Gitpod

@YaelDillies YaelDillies added the RFC Request for comment label Feb 3, 2026
@github-actions github-actions bot added the t-combinatorics Combinatorics label Feb 3, 2026
@github-actions
Copy link
Copy Markdown

github-actions bot commented Feb 3, 2026

PR summary f7c1d6ebc9

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ IsIsolated
+ IsIsolated.degree_eq_zero
+ IsIsolated.neighborFinset_eq_empty
+ IsIsolated.neighborSet_eq_empty
+ IsIsolated.of_degree_eq_zero
+ IsIsolated.of_neighborFinset_eq_empty
+ IsIsolated.of_neighborSet_eq_empty
+ Preconnected.not_isIsolated
+ degree_eq_zero
+ degree_pos
+ mem_support_iff_not_isIsolated
+ neighborFinset_eq_empty
+ neighborFinset_nonempty
+ neighborSet_eq_empty
+ neighborSet_nonempty

You can run this locally as follows
## summary with just the declaration names:
./scripts/pr_summary/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/pr_summary/declarations_diff.sh long <optional_commit>

The doc-module for scripts/pr_summary/declarations_diff.sh contains some details about this script.


No changes to technical debt.

You can run this locally as

./scripts/reporting/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

Comment thread Mathlib/Combinatorics/SimpleGraph/Finite.lean Outdated
Comment thread Mathlib/Combinatorics/SimpleGraph/Basic.lean Outdated
Comment thread Mathlib/Combinatorics/SimpleGraph/Basic.lean Outdated
@b-mehta b-mehta added the awaiting-author A reviewer has asked the author a question or requested changes. label Mar 27, 2026
RFC for now. Do you think this is a reasonable definition to have? What should its API be?

From ProofBench
@YaelDillies YaelDillies force-pushed the simple_graph_isolated branch from fdfc5e2 to 50ab40e Compare March 29, 2026 07:22
@YaelDillies YaelDillies removed the awaiting-author A reviewer has asked the author a question or requested changes. label Mar 29, 2026
Comment thread Mathlib/Combinatorics/SimpleGraph/Connectivity/Connected.lean
Comment thread Mathlib/Combinatorics/SimpleGraph/Finite.lean Outdated
@b-mehta
Copy link
Copy Markdown
Contributor

b-mehta commented Apr 10, 2026

I think this is reasonable, but just to check, what's the actual reason it's better to have this predicate and not just talk about emptiness of G.neighborSet v?

@YaelDillies
Copy link
Copy Markdown
Contributor Author

My reasoning is that there are many equivalent ways to write this condition (I can think of five that work in full generality), none of which seems particularly preferred, and I wanted to unify them all to a single new one for clarity and discoverability. It also happens to enable dot notation and correspond to a well-established informal notion

@b-mehta
Copy link
Copy Markdown
Contributor

b-mehta commented Apr 10, 2026

Makes sense, have you added the lemmas relating this to all five?

bors d+

@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Apr 10, 2026

✌️ YaelDillies can now approve this pull request. To approve and merge a pull request, simply reply with bors r+. More detailed instructions are available here.

@mathlib-triage mathlib-triage bot added the delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). label Apr 10, 2026
@YaelDillies
Copy link
Copy Markdown
Contributor Author

Here are the five seven I was thinking of, along with the lemmas proving they are equivalent to G.IsIsolated v:

  • ∀ w, ¬ G.Adj v w, equational lemma for IsIsolated
  • ∀ w, ¬ G.Adj w v, equational lemma for IsIsolated and adj_comm
  • v ∉ G.support, mem_support_iff_not_isIsolated and not_not
  • G.neighborSet v = ∅, neighborSet_eq_empty
  • G.neighborFinset v = ∅, neighborFinset_eq_empty
  • G.degree = 0, degree_eq_zero
  • G.edegree = 0, missing because edegree doesn't exist yet

bors merge

mathlib-bors bot pushed a commit that referenced this pull request Apr 13, 2026
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Apr 13, 2026

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title feat(Combinatorics/SimpleGraph): isolated vertices [Merged by Bors] - feat(Combinatorics/SimpleGraph): isolated vertices Apr 13, 2026
@mathlib-bors mathlib-bors bot closed this Apr 13, 2026
@YaelDillies YaelDillies deleted the simple_graph_isolated branch April 13, 2026 11:29
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). t-combinatorics Combinatorics

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants