feat(combinatorics/simple_graph/connectivity): number of connected components when deleting edges #17654
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Add definition for number of connected components and then prove that this number either goes up by 1 or is unchanged when an edge is removed, depending on if its in a cycle or not.
tjeremie
added
awaiting-review
|
Could you fix the style errors? |
Should be fixed now |
kmill
changed the title
kmill
reviewed
Nov 21, 2022
| @@ -697,6 +705,8 @@ lemma edge_finset_delete_edges [fintype V] [decidable_eq V] [decidable_rel G.adj | |||
| (G.delete_edges s).edge_finset = G.edge_finset \ s := | |||
| by { ext e, simp [edge_set_delete_edges] } | |||
|
|
|||
| lemma delete_non_edge {e: sym2 V} (he: e ∉ G.edge_set) : G.delete_edges {e} = G := by {ext,finish} | |||
There was a problem hiding this comment.
Note that finish has now been banned in mathlib3 since it's not going to be ported to Lean 4.
There are some more general results we should add here, in place of delete_non_edge.
lemma delete_edges_eq_self_iff_disjoint {s : set (sym2 V)} :
G.delete_edges s = G ↔ disjoint G.edge_set s :=
begin
rw [set.disjoint_left, simple_graph.ext_iff],
simp only [function.funext_iff, delete_edges_adj, eq_iff_iff, and_iff_left_iff_imp],
split,
{ intro h,
refine sym2.ind (λ v w, _),
exact h v w, },
{ intros h v w hvw,
rw ← mem_edge_set at hvw,
exact h hvw, }
end
lemma delete_edges_singleton_eq_self_iff_not_mem :
G.delete_edges {e} = G ↔ e ∉ G.edge_set :=
by rw [delete_edges_eq_self_iff_disjoint, set.disjoint_singleton_right]I should mention that mathlib3 style is that type ascription colons should have a space on both sides, so {e : sym2 V} rather than {e: sym2 V}.
There was a problem hiding this comment.
I would make both of those lemmas simp.
Comment on lines
530
to
531
| lemma darts_nodup_of_edges_nodup {u v : V} {p : G.walk u v} (h : p.edges.nodup) : p.darts.nodup | ||
| :=list.nodup.of_map dart.edge h |
There was a problem hiding this comment.
Mathlib3 style:
Suggested change
| lemma darts_nodup_of_edges_nodup {u v : V} {p : G.walk u v} (h : p.edges.nodup) : p.darts.nodup | |
| :=list.nodup.of_map dart.edge h | |
| lemma darts_nodup_of_edges_nodup {u v : V} {p : G.walk u v} (h : p.edges.nodup) : p.darts.nodup := | |
| list.nodup.of_map dart.edge h |
kmill
added
awaiting-author
Co-authored-by: Kyle Miller <kmill31415@gmail.com>
…unity/mathlib into graphs_num_comps Merging suggested edit with local edits
|
Thanks for your various comments! Sorry for the delay, but I think I've now fixed everything you mentioned (as well as similar issues later in the code). Let me know what you think |
tjeremie
added
awaiting-review
semorrison
added
the
too-late
|
This PR is on my radar, and while it missed the mathlib3 cutoff, I'm hoping to (eventually) get it ported to mathlib4! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Add definition for number of connected components and then prove that this number either goes up by 1 or is unchanged when an edge is removed, depending on if its in a cycle or not.