Documentation Verification Report

Connected

πŸ“ Source: Mathlib/Combinatorics/SimpleGraph/Connectivity/Connected.lean

Statistics

MetricCount
DefinitionsConnected, inhabited, instSetLike, instUnique, isoEquivSupp, map, recOn, supp, toSimpleGraph, toSimpleGraph_hom, IsBridge, connectedComponentEquiv, Preconnected, Reachable, Connected, connectedComponentMk, homOfConnectedComponents, instCoeFunConnectedForallForallReachable, reachableSetoid
19
Theoremsreachable, connected_delete_edge_of_not_isBridge, exists_isPath, map, mono, nonempty, of_subsingleton, preconnected, set_univ_walk_nonempty, adj_spanningCoe_toSimpleGraph, biUnion_supp_eq_supp, connectedComponentMk_eq_of_adj, connectedComponentMk_mem, connectedComponentMk_supp_subset_supp, connected_toSimpleGraph, eq, eq_of_common_vertex, exact, exists, forall, ind, indβ‚‚, inhabited_default, instFinite, instNonempty, instSubsingleton, isEmpty, iso_image_comp_eq_map_iff_eq_comp, iso_inv_image_comp_eq_iff_eq_map, lift_mk, map_comp, map_id, map_mk, maximal_connected_induce_iff, maximal_connected_induce_supp, mem_coe_supp_of_adj, mem_supp_congr_adj, mem_supp_iff, mem_supp_of_adj_mem_supp, nonempty_supp, reachable_of_mem_supp, reachable_toSimpleGraph, sound, supp_inj, supp_injective, supp_injective_iff, surjective_map_ofLE, toSimpleGraph_adj, toSimpleGraph_hom_apply, top_supp_eq_univ, anti_of_mem_edgeSet, connectedComponentEquiv_apply, connectedComponentEquiv_refl, connectedComponentEquiv_symm, connectedComponentEquiv_symm_apply, connectedComponentEquiv_trans, connected_iff, preconnected_iff, reachable_iff, symm_apply_reachable, degree_pos_of_nontrivial, exists_adj_of_nontrivial, exists_isPath, induce_of_degree_eq_one, map, minDegree_pos_of_nontrivial, mono, of_subsingleton, set_univ_walk_nonempty, subsingleton_connectedComponent, support_eq_univ, elim, elim_path, exists_isPath, map, mem_subgraphVerts, mono, mono', of_subsingleton, refl, rfl, trans, not_mem_edges_of_not_reachable, not_mem_support_of_not_reachable, not_mem_support_of_subsingleton_neighborSet, exists_mem_edges_of_not_reachable_deleteEdges, mem_edges_of_not_reachable_deleteEdges, reachable, adj_and_reachable_delete_edges_iff_exists_cycle, adj_le_reachable, adj_of_mem_walk_support, bot_not_connected, bot_not_preconnected, bot_preconnected, bot_preconnected_iff_subsingleton, connected_bot_iff, connected_iff, connected_iff_exists_forall_reachable, connected_or_connected_compl, connected_or_preconnected_compl, connected_top, connected_top_iff, homOfConnectedComponents_apply, iUnion_connectedComponentSupp, isBridge_iff, isBridge_iff_adj_and_forall_cycle_notMem, isBridge_iff_adj_and_forall_walk_mem_edges, isBridge_iff_mem_and_forall_cycle_notMem, mem_support_of_mem_walk_support, mem_support_of_reachable, not_connected_bot, not_preconnected_bot, not_reachable_iff_isEmpty_walk, not_reachable_of_left_degree_zero, not_reachable_of_right_degree_zero, pairwise_disjoint_supp_connectedComponent, preconnected_bot, preconnected_bot_iff_subsingleton, preconnected_iff_reachable_eq_top, preconnected_top, reachable_bot, reachable_comm, aux, reachable_delete_edges_iff_exists_walk, reachable_eq_reflTransGen, reachable_fromEdgeSet_eq_reflTransGen_toRel, reachable_fromEdgeSet_fromRel_eq_reflTransGen, reachable_iff_nonempty_univ, reachable_iff_reflTransGen, reachable_is_equivalence, reachable_or_compl_adj, reachable_or_reachable_compl, reachable_top, top_connected, top_preconnected
135
Total154

SimpleGraph

Definitions

NameCategoryTheorems
Connected πŸ“–CompData
38 mathmath: connected_top, ConnectedComponent.maximal_connected_induce_supp, connected_iff_ediam_ne_top, induce_connected_of_patches, bot_not_connected, connected_of_ediam_ne_top, isTree_iff, extend_finset_to_connected, isTree_iff_minimal_connected, ConnectedComponent.maximal_connected_induce_iff, induce_union_connected, IsTree.isConnected, IsHamiltonian.connected, isTree_iff_connected_and_card, connected_or_connected_compl, induce_pair_connected_of_adj, pathGraph_connected, cycleGraph_connected, not_connected_bot, top_connected, connected_top_iff, connected_bot_iff, ConnectedComponent.connected_toSimpleGraph, connected_iff_diam_ne_zero, Subgraph.connected_iff', connected_induce_iff, Iso.connected_iff, Connected.of_subsingleton, connected_induce_union, radius_ne_top_iff, IsEdgeConnected.connected, connected_or_preconnected_compl, connected_iff, Subgraph.Connected.induce_verts, connected_iff_exists_forall_reachable, Walk.connected_induce_support, connected_boxProd, Subgraph.Connected.coe
IsBridge πŸ“–MathDef
7 mathmath: isAcyclic_iff_forall_adj_isBridge, isBridge_iff_adj_and_forall_walk_mem_edges, isAcyclic_iff_forall_edge_isBridge, isBridge_iff, isBridge_iff_adj_and_forall_cycle_notMem, isBridge_iff_adj_and_not_isEdgeConnected_two, isBridge_iff_mem_and_forall_cycle_notMem
Preconnected πŸ“–MathDef
26 mathmath: Connected.preconnected, isEdgeConnected_two, hasse_preconnected_of_pred, bot_not_preconnected, preconnected_iff_reachable_eq_top, Iso.preconnected_iff, preconnected_of_ediam_ne_top, Preconnected.of_subsingleton, preconnected_top, Subgraph.preconnected_iff, preconnected_bot, hasse_preconnected_of_succ, Connected.exists_preconnected_induce_compl_singleton_of_finite, Subgraph.Preconnected.coe, IsEdgeConnected.preconnected, isEdgeConnected_one, preconnected_induce_iff, bot_preconnected_iff_subsingleton, top_preconnected, pathGraph_preconnected, preconnected_bot_iff_subsingleton, connected_or_preconnected_compl, connected_iff, cycleGraph_preconnected, not_preconnected_bot, bot_preconnected
Reachable πŸ“–MathDef
57 mathmath: Reachable.symm, reachable_iff_nonempty_univ, ConnectedComponent.reachable_toSimpleGraph, Iso.reachable_iff, Reachable.mono', Iso.symm_apply_reachable, Reachable.of_subsingleton, IsCycles.reachable_sdiff_toSubgraph_spanningCoe, reachable_or_reachable_compl, not_reachable_of_right_degree_zero, preconnected_iff_reachable_eq_top, Adj.reachable, reachable_iff_exists_finsetWalkLength_nonempty, reachable_delete_edges_iff_exists_walk, reachable_is_equivalence, edist_ne_top_iff_reachable, Walk.reachable, adj_and_reachable_delete_edges_iff_exists_cycle, isEdgeReachable_two, isEdgeReachable_one, reachable_fromEdgeSet_eq_reflTransGen_toRel, Reachable.sum_sup_edge, not_reachable_iff_isEmpty_walk, dist_ne_zero_iff_ne_and_reachable, Reachable.coe_coeSubgraph, Reachable.trans, ConnectedComponent.Represents.image_out, ConnectedComponent.reachable_of_mem_supp, isBridge_iff, reachable_boxProd, reachable_eq_of_maximal_isAcyclic, exists_isAcyclic_reachable_eq_le_of_le_of_isAcyclic, Reachable.map, reachable_bot, reachable_iff_reflTransGen, IsEdgeReachable.reachable, Reachable.mono, Reachable.rfl, maximal_isAcyclic_iff_reachable_eq, IsCycles.reachable_deleteEdges, dist_eq_zero_iff_eq_or_not_reachable, ConnectedComponent.eq, reachable_of_edist_ne_top, reachable_or_compl_adj, Reachable.coe_toSubgraph, reachable_top, Reachable.coe_subgraphMap, adj_le_reachable, ConnectedComponent.exact, not_reachable_of_left_degree_zero, reachable_fromEdgeSet_fromRel_eq_reflTransGen, reachable_eq_reflTransGen, reachable_comm, Reachable.of_dist_ne_zero, exists_isAcyclic_reachable_eq_le, connected_iff_exists_forall_reachable, Reachable.refl
connectedComponentMk πŸ“–CompOp
15 mathmath: homOfConnectedComponents_apply, ConnectedComponent.iso_inv_image_comp_eq_iff_eq_map, ConnectedComponent.connectedComponentMk_mem, ConnectedComponent.lift_mk, ConnectedComponent.iso_image_comp_eq_map_iff_eq_comp, ConnectedComponent.mem_supp_iff, ConnectedComponent.exists, ConnectedComponent.connectedComponentMk_supp_subset_supp, ConnectedComponent.map_mk, ConnectedComponent.eq, ConnectedComponent.connectedComponentMk_eq_of_adj, ConnectedComponent.inhabited_default, ConnectedComponent.sound, ConnectedComponent.forall, mem_ker_toLin'_lapMatrix_of_connectedComponent
homOfConnectedComponents πŸ“–CompOp
1 mathmath: homOfConnectedComponents_apply
instCoeFunConnectedForallForallReachable πŸ“–CompOpβ€”
reachableSetoid πŸ“–CompOpβ€”

Theorems

NameKindAssumesProvesValidatesDepends On
adj_and_reachable_delete_edges_iff_exists_cycle πŸ“–mathematicalβ€”Adj
Reachable
SimpleGraph
sdiff
fromEdgeSet
Sym2
Set
Set.instSingletonSet
Walk.IsCycle
Walk.edges
β€”reachable_delete_edges_iff_exists_walk
Adj.symm
Path.cons_isCycle
Sym2.eq_swap
Walk.edges_toPath_subset
Walk.adj_of_mem_edges
Walk.edges_reverse
Walk.fst_mem_support_of_mem_edges
reachable_deleteEdges_iff_exists_cycle.aux
Walk.IsTrail.rotate
Walk.IsCircuit.isTrail
Walk.IsCycle.isCircuit
List.IsRotated.mem_iff
Walk.rotate_edges
Walk.start_mem_support
adj_le_reachable πŸ“–mathematicalβ€”Pi.hasLe
Prop.le
Adj
Reachable
β€”Adj.reachable
adj_of_mem_walk_support πŸ“–mathematicalWalk.Nil
Walk.support
Adjβ€”β€”
bot_not_connected πŸ“–mathematicalβ€”Connected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”not_connected_bot
bot_not_preconnected πŸ“–mathematicalβ€”Preconnected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”not_preconnected_bot
bot_preconnected πŸ“–mathematicalβ€”Preconnected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”preconnected_bot
bot_preconnected_iff_subsingleton πŸ“–mathematicalβ€”Preconnected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”preconnected_bot_iff_subsingleton
connected_bot_iff πŸ“–mathematicalβ€”Connected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”β€”
connected_iff πŸ“–mathematicalβ€”Connected
Preconnected
β€”β€”
connected_iff_exists_forall_reachable πŸ“–mathematicalβ€”Connected
Reachable
β€”connected_iff
Reachable.trans
Reachable.symm
connected_or_connected_compl πŸ“–mathematicalβ€”Connected
Compl.compl
SimpleGraph
instCompl
β€”connected_or_preconnected_compl
connected_or_preconnected_compl πŸ“–mathematicalβ€”Connected
Preconnected
Compl.compl
SimpleGraph
instCompl
β€”connected_iff_exists_forall_reachable
Mathlib.Tactic.Push.not_forall_eq
reachable_or_reachable_compl
connected_top πŸ“–mathematicalβ€”Connected
completeGraph
β€”connected_top_iff
connected_top_iff πŸ“–mathematicalβ€”Connected
completeGraph
β€”β€”
homOfConnectedComponents_apply πŸ“–mathematicalβ€”DFunLike.coe
RelHom
Adj
RelHom.instFunLike
homOfConnectedComponents
Hom
ConnectedComponent
SetLike.instMembership
ConnectedComponent.instSetLike
connectedComponentMk
ConnectedComponent.toSimpleGraph
ConnectedComponent.connectedComponentMk_mem
β€”β€”
iUnion_connectedComponentSupp πŸ“–mathematicalβ€”Set.iUnion
ConnectedComponent
ConnectedComponent.supp
Set.univ
β€”Set.eq_univ_of_forall
isBridge_iff πŸ“–mathematicalβ€”IsBridge
Adj
Reachable
SimpleGraph
sdiff
fromEdgeSet
Sym2
Set
Set.instSingletonSet
β€”β€”
isBridge_iff_adj_and_forall_cycle_notMem πŸ“–mathematicalβ€”IsBridge
Adj
Sym2
Walk.edges
β€”isBridge_iff
Mathlib.Tactic.Contrapose.contrapose_iffβ‚‚
Mathlib.Tactic.Push.not_forall_eq
adj_and_reachable_delete_edges_iff_exists_cycle
isBridge_iff_adj_and_forall_walk_mem_edges πŸ“–mathematicalβ€”IsBridge
Adj
Sym2
Walk.edges
β€”isBridge_iff
reachable_delete_edges_iff_exists_walk
isBridge_iff_mem_and_forall_cycle_notMem πŸ“–mathematicalβ€”IsBridge
Sym2
Set
Set.instMembership
edgeSet
Walk.edges
β€”Sym2.ind
isBridge_iff_adj_and_forall_cycle_notMem
mem_support_of_mem_walk_support πŸ“–mathematicalWalk.Nil
Walk.support
Set
Set.instMembership
support
β€”adj_of_mem_walk_support
mem_support
mem_support_of_reachable πŸ“–mathematicalβ€”Set
Set.instMembership
support
β€”Walk.not_nil_of_ne
mem_support_of_mem_walk_support
Walk.start_mem_support
not_connected_bot πŸ“–mathematicalβ€”Connected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”β€”
not_preconnected_bot πŸ“–mathematicalβ€”Preconnected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”Iff.not
preconnected_bot_iff_subsingleton
not_subsingleton_iff_nontrivial
not_reachable_iff_isEmpty_walk πŸ“–mathematicalβ€”Reachable
IsEmpty
Walk
β€”not_nonempty_iff
not_reachable_of_left_degree_zero πŸ“–mathematicaldegreeReachableβ€”degree_pos_iff_exists_adj
not_reachable_of_right_degree_zero πŸ“–mathematicaldegreeReachableβ€”reachable_comm
not_reachable_of_left_degree_zero
pairwise_disjoint_supp_connectedComponent πŸ“–mathematicalβ€”Pairwise
ConnectedComponent
Disjoint
Set
CompleteSemilatticeInf.toPartialOrder
CompleteLattice.toCompleteSemilatticeInf
CompleteBooleanAlgebra.toCompleteLattice
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
Set.instCompleteAtomicBooleanAlgebra
HeytingAlgebra.toOrderBot
Order.Frame.toHeytingAlgebra
CompleteDistribLattice.toFrame
CompleteBooleanAlgebra.toCompleteDistribLattice
ConnectedComponent.supp
β€”ConnectedComponent.mem_supp_iff
preconnected_bot πŸ“–mathematicalβ€”Preconnected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”preconnected_bot_iff_subsingleton
preconnected_bot_iff_subsingleton πŸ“–mathematicalβ€”Preconnected
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”Mathlib.Tactic.Contrapose.contrapose₁
nontrivial_iff
preconnected_iff_reachable_eq_top πŸ“–mathematicalβ€”Preconnected
Reachable
Top.top
Pi.instTopForall
BooleanAlgebra.toTop
Prop.instBooleanAlgebra
β€”β€”
preconnected_top πŸ“–mathematicalβ€”Preconnected
Top.top
SimpleGraph
BooleanAlgebra.toTop
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”Reachable.refl
Adj.reachable
reachable_bot πŸ“–mathematicalβ€”Reachable
Bot.bot
SimpleGraph
BooleanAlgebra.toBot
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”Reachable.elim
Reachable.rfl
reachable_comm πŸ“–mathematicalβ€”Reachableβ€”Reachable.symm
reachable_delete_edges_iff_exists_walk πŸ“–mathematicalβ€”Reachable
SimpleGraph
sdiff
fromEdgeSet
Sym2
Set
Set.instSingletonSet
Walk.edges
β€”Walk.edges_map
Sym2.map_congr
Sym2.map_id'
edgeSet_sdiff
edgeSet_fromEdgeSet
edgeSet_sdiff_sdiff_isDiag
Walk.edges_subset_edgeSet
reachable_eq_reflTransGen πŸ“–mathematicalβ€”Reachable
Relation.ReflTransGen
Adj
β€”reachable_iff_reflTransGen
reachable_fromEdgeSet_eq_reflTransGen_toRel πŸ“–mathematicalβ€”Reachable
fromEdgeSet
Relation.ReflTransGen
Sym2.ToRel
β€”reachable_eq_reflTransGen
Relation.transGen_reflGen
reachable_fromEdgeSet_fromRel_eq_reflTransGen πŸ“–mathematicalSymmetricReachable
fromEdgeSet
Sym2.fromRel
Relation.ReflTransGen
β€”reachable_fromEdgeSet_eq_reflTransGen_toRel
reachable_iff_nonempty_univ πŸ“–mathematicalβ€”Reachable
Set.Nonempty
Walk
Set.univ
β€”Set.nonempty_iff_univ_nonempty
reachable_iff_reflTransGen πŸ“–mathematicalβ€”Reachable
Relation.ReflTransGen
Adj
β€”Relation.ReflTransGen.trans
Relation.ReflTransGen.single
Reachable.refl
Reachable.trans
reachable_is_equivalence πŸ“–mathematicalβ€”Reachableβ€”Reachable.refl
Reachable.symm
Reachable.trans
reachable_or_compl_adj πŸ“–mathematicalβ€”Reachable
Adj
Compl.compl
SimpleGraph
instCompl
β€”Reachable.rfl
Adj.reachable
reachable_or_reachable_compl πŸ“–mathematicalβ€”Reachable
Compl.compl
SimpleGraph
instCompl
β€”reachable_or_compl_adj
Reachable.trans
Reachable.symm
Adj.reachable
reachable_top πŸ“–mathematicalβ€”Reachable
completeGraph
β€”eq_or_ne
top_connected πŸ“–mathematicalβ€”Connected
completeGraph
β€”connected_top
top_preconnected πŸ“–mathematicalβ€”Preconnected
Top.top
SimpleGraph
BooleanAlgebra.toTop
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
completeAtomicBooleanAlgebra
β€”preconnected_top

SimpleGraph.Adj

Theorems

NameKindAssumesProvesValidatesDepends On
reachable πŸ“–mathematicalSimpleGraph.AdjSimpleGraph.Reachableβ€”SimpleGraph.Walk.reachable

SimpleGraph.Connected

Theorems

NameKindAssumesProvesValidatesDepends On
connected_delete_edge_of_not_isBridge πŸ“–mathematicalSimpleGraph.Connected
SimpleGraph.IsBridge
SimpleGraph.deleteEdges
Sym2
Set
Set.instSingletonSet
β€”em'
SimpleGraph.deleteEdges.eq_1
Disjoint.sdiff_eq_left
SimpleGraph.connected_iff_exists_forall_reachable
exists_isPath
SimpleGraph.Walk.snd_mem_support_of_mem_edges
SimpleGraph.Walk.endpoint_notMem_support_takeUntil
SimpleGraph.Adj.ne
SimpleGraph.Walk.fst_mem_support_of_mem_edges
SimpleGraph.Reachable.trans
SimpleGraph.Reachable.symm
exists_isPath πŸ“–mathematicalSimpleGraph.ConnectedSimpleGraph.Walk.IsPathβ€”SimpleGraph.Reachable.exists_isPath
preconnected
map πŸ“–β€”DFunLike.coe
SimpleGraph.Hom
RelHom.instFunLike
SimpleGraph.Adj
SimpleGraph.Connected
β€”β€”SimpleGraph.Preconnected.map
preconnected
Nonempty.map
nonempty
mono πŸ“–β€”SimpleGraph
SimpleGraph.instLE
SimpleGraph.Connected
β€”β€”SimpleGraph.Preconnected.mono
preconnected
nonempty
nonempty πŸ“–β€”SimpleGraph.Connectedβ€”β€”β€”
of_subsingleton πŸ“–mathematicalβ€”SimpleGraph.Connectedβ€”SimpleGraph.Preconnected.of_subsingleton
preconnected πŸ“–mathematicalSimpleGraph.ConnectedSimpleGraph.Preconnectedβ€”β€”
set_univ_walk_nonempty πŸ“–mathematicalSimpleGraph.ConnectedSet.Nonempty
SimpleGraph.Walk
Set.univ
β€”SimpleGraph.Preconnected.set_univ_walk_nonempty
preconnected

SimpleGraph.ConnectedComponent

Definitions

NameCategoryTheorems
inhabited πŸ“–CompOp
1 mathmath: inhabited_default
instSetLike πŸ“–CompOp
9 mathmath: SimpleGraph.colorable_iff_forall_connectedComponents, SimpleGraph.homOfConnectedComponents_apply, SimpleGraph.IsCycles.toSimpleGraph, adj_spanningCoe_toSimpleGraph, connectedComponentMk_mem, toSimpleGraph_hom_apply, spanningCoe_toSubgraph, connected_toSimpleGraph, SimpleGraph.IsAcyclic.isTree_connectedComponent
instUnique πŸ“–CompOpβ€”
isoEquivSupp πŸ“–CompOpβ€”
map πŸ“–CompOp
8 mathmath: SimpleGraph.Iso.connectedComponentEquiv_symm_apply, map_id, iso_inv_image_comp_eq_iff_eq_map, surjective_map_ofLE, iso_image_comp_eq_map_iff_eq_comp, map_comp, map_mk, SimpleGraph.Iso.connectedComponentEquiv_apply
recOn πŸ“–CompOpβ€”
supp πŸ“–CompOp
28 mathmath: supp_injective, SimpleGraph.Subgraph.IsPerfectMatching.induce_connectedComponent_isMatching, maximal_connected_induce_supp, SimpleGraph.iUnion_connectedComponentSupp, mem_supp_congr_adj, SimpleGraph.disjiUnion_supp_toFinset_eq_supp_toFinset, SimpleGraph.Subgraph.IsMatching.induce_connectedComponent, even_ncard_supp_sdiff_rep, supp_injective_iff, even_card_of_isPerfectMatching, maximal_connected_induce_iff, Represents.ncard_sdiff_of_mem, odd_matches_node_outside, Represents.exists_inter_eq_singleton, top_supp_eq_univ, adj_spanningCoe_toSimpleGraph, SimpleGraph.Subgraph.Connected.exists_verts_eq_connectedComponentSupp, SimpleGraph.pairwise_disjoint_supp_connectedComponent, mem_supp_iff, SimpleGraph.even_ncard_image_val_supp_sdiff_image_val_rep_union, Represents.ncard_inter, Represents.ncard_sdiff_of_notMem, Represents.existsUnique_rep, supp_inj, odd_oddComponents_ncard_subset_supp, biUnion_supp_eq_supp, Represents.disjoint_supp_of_notMem, nonempty_supp
toSimpleGraph πŸ“–CompOp
11 mathmath: SimpleGraph.colorable_iff_forall_connectedComponents, SimpleGraph.homOfConnectedComponents_apply, reachable_toSimpleGraph, coe_toSubgraph, SimpleGraph.IsCycles.toSimpleGraph, adj_spanningCoe_toSimpleGraph, toSimpleGraph_hom_apply, spanningCoe_toSubgraph, connected_toSimpleGraph, SimpleGraph.IsAcyclic.isTree_connectedComponent, toSimpleGraph_adj
toSimpleGraph_hom πŸ“–CompOp
1 mathmath: toSimpleGraph_hom_apply

Theorems

NameKindAssumesProvesValidatesDepends On
adj_spanningCoe_toSimpleGraph πŸ“–mathematicalβ€”SimpleGraph.Adj
SimpleGraph.spanningCoe
SetLike.coe
SimpleGraph.ConnectedComponent
instSetLike
toSimpleGraph
Set
Set.instMembership
supp
β€”mem_supp_congr_adj
biUnion_supp_eq_supp πŸ“–mathematicalSimpleGraph
SimpleGraph.instLE
Set.iUnion
SimpleGraph.ConnectedComponent
Set
Set.instHasSubset
supp
β€”Set.ext
connectedComponentMk_supp_subset_supp
connectedComponentMk_eq_of_adj πŸ“–mathematicalSimpleGraph.AdjSimpleGraph.connectedComponentMkβ€”sound
SimpleGraph.Adj.reachable
connectedComponentMk_mem πŸ“–mathematicalβ€”SimpleGraph.ConnectedComponent
SetLike.instMembership
instSetLike
SimpleGraph.connectedComponentMk
β€”β€”
connectedComponentMk_supp_subset_supp πŸ“–mathematicalSimpleGraph
SimpleGraph.instLE
Set
Set.instMembership
supp
Set.instHasSubset
SimpleGraph.connectedComponentMk
β€”sound
SimpleGraph.Reachable.mono
connected_toSimpleGraph πŸ“–mathematicalβ€”SimpleGraph.Connected
SimpleGraph.ConnectedComponent
SetLike.instMembership
instSetLike
toSimpleGraph
β€”reachable_toSimpleGraph
Quot.out_eq
eq πŸ“–mathematicalβ€”SimpleGraph.connectedComponentMk
SimpleGraph.Reachable
β€”Quotient.eq'
eq_of_common_vertex πŸ“–β€”Set
Set.instMembership
supp
β€”β€”β€”
exact πŸ“–mathematicalSimpleGraph.connectedComponentMkSimpleGraph.Reachableβ€”β€”
exists πŸ“–mathematicalβ€”SimpleGraph.connectedComponentMkβ€”Function.Surjective.exists
Quot.mk_surjective
forall πŸ“–mathematicalβ€”SimpleGraph.connectedComponentMkβ€”Function.Surjective.forall
Quot.mk_surjective
ind πŸ“–β€”SimpleGraph.connectedComponentMkβ€”β€”β€”
indβ‚‚ πŸ“–β€”SimpleGraph.connectedComponentMkβ€”β€”Quot.induction_onβ‚‚
inhabited_default πŸ“–mathematicalβ€”SimpleGraph.ConnectedComponent
inhabited
SimpleGraph.connectedComponentMk
β€”β€”
instFinite πŸ“–mathematicalβ€”Finite
SimpleGraph.ConnectedComponent
β€”Quot.finite
instNonempty πŸ“–mathematicalβ€”SimpleGraph.ConnectedComponentβ€”Nonempty.map
instSubsingleton πŸ“–mathematicalβ€”SimpleGraph.ConnectedComponentβ€”Quot.Subsingleton
isEmpty πŸ“–mathematicalβ€”IsEmpty
SimpleGraph.ConnectedComponent
β€”Quot.instIsEmpty
iso_image_comp_eq_map_iff_eq_comp πŸ“–mathematicalβ€”SimpleGraph.connectedComponentMk
DFunLike.coe
SimpleGraph.Iso
RelIso.instFunLike
SimpleGraph.Adj
map
RelEmbedding.toRelHom
RelIso.toRelEmbedding
β€”ind
iso_inv_image_comp_eq_iff_eq_map πŸ“–mathematicalβ€”SimpleGraph.connectedComponentMk
DFunLike.coe
SimpleGraph.Iso
RelIso.instFunLike
SimpleGraph.Adj
SimpleGraph.Iso.symm
map
RelEmbedding.toRelHom
RelIso.toRelEmbedding
β€”ind
lift_mk πŸ“–mathematicalβ€”lift
SimpleGraph.connectedComponentMk
β€”β€”
map_comp πŸ“–mathematicalβ€”map
SimpleGraph.Hom.comp
β€”ind
map_id πŸ“–mathematicalβ€”map
SimpleGraph.Hom.id
β€”ind
map_mk πŸ“–mathematicalβ€”map
SimpleGraph.connectedComponentMk
DFunLike.coe
SimpleGraph.Hom
RelHom.instFunLike
SimpleGraph.Adj
β€”β€”
maximal_connected_induce_iff πŸ“–mathematicalβ€”Maximal
Set
Set.instLE
SimpleGraph.Connected
Set.Elem
SimpleGraph.induce
supp
β€”SimpleGraph.Connected.nonempty
sound
SimpleGraph.Reachable.map
SimpleGraph.Connected.preconnected
le_antisymm
connected_toSimpleGraph
maximal_connected_induce_supp
maximal_connected_induce_supp πŸ“–mathematicalβ€”Maximal
Set
Set.instLE
SimpleGraph.Connected
Set.Elem
SimpleGraph.induce
supp
β€”ind
connected_toSimpleGraph
sound
SimpleGraph.Reachable.map
SimpleGraph.Connected.preconnected
mem_coe_supp_of_adj πŸ“–β€”Set
Set.instMembership
Set.image
Set.Elem
SimpleGraph.Subgraph.verts
SetLike.coe
SimpleGraph.ConnectedComponent
SimpleGraph.Subgraph.coe
instSetLike
SimpleGraph.Subgraph.Adj
β€”β€”mem_supp_iff
connectedComponentMk_eq_of_adj
SimpleGraph.Subgraph.Adj.coe
SimpleGraph.Subgraph.Adj.symm
mem_supp_congr_adj πŸ“–mathematicalSimpleGraph.AdjSet
Set.instMembership
supp
β€”connectedComponentMk_eq_of_adj
SimpleGraph.Adj.symm
mem_supp_iff πŸ“–mathematicalβ€”Set
Set.instMembership
supp
SimpleGraph.connectedComponentMk
β€”β€”
mem_supp_of_adj_mem_supp πŸ“–β€”Set
Set.instMembership
supp
SimpleGraph.Adj
β€”β€”mem_supp_congr_adj
nonempty_supp πŸ“–mathematicalβ€”Set.Nonempty
supp
β€”β€”
reachable_of_mem_supp πŸ“–mathematicalSet
Set.instMembership
supp
SimpleGraph.Reachableβ€”exact
mem_supp_iff
reachable_toSimpleGraph πŸ“–mathematicalSimpleGraph.ConnectedComponent
SetLike.instMembership
instSetLike
SimpleGraph.Reachable
toSimpleGraph
β€”SimpleGraph.Walk.reachable
reachable_of_mem_supp
sound πŸ“–mathematicalβ€”SimpleGraph.connectedComponentMkβ€”β€”
supp_inj πŸ“–mathematicalβ€”suppβ€”supp_injective
supp_injective πŸ“–mathematicalβ€”SimpleGraph.ConnectedComponent
Set
supp
β€”indβ‚‚
SimpleGraph.reachable_comm
SimpleGraph.Reachable.refl
supp_injective_iff πŸ“–mathematicalβ€”suppβ€”supp_injective
surjective_map_ofLE πŸ“–mathematicalSimpleGraph
SimpleGraph.instLE
SimpleGraph.ConnectedComponent
map
SimpleGraph.Hom.ofLE
β€”β€”
toSimpleGraph_adj πŸ“–mathematicalSimpleGraph.ConnectedComponent
SetLike.instMembership
instSetLike
SimpleGraph.Adj
toSimpleGraph
β€”β€”
toSimpleGraph_hom_apply πŸ“–mathematicalβ€”DFunLike.coe
SimpleGraph.Hom
SimpleGraph.ConnectedComponent
SetLike.instMembership
instSetLike
toSimpleGraph
RelHom.instFunLike
SimpleGraph.Adj
toSimpleGraph_hom
β€”β€”
top_supp_eq_univ πŸ“–mathematicalβ€”supp
Top.top
SimpleGraph
BooleanAlgebra.toTop
CompleteBooleanAlgebra.toBooleanAlgebra
CompleteAtomicBooleanAlgebra.toCompleteBooleanAlgebra
SimpleGraph.completeAtomicBooleanAlgebra
Set.univ
β€”Set.ext
sound

SimpleGraph.IsBridge

Theorems

NameKindAssumesProvesValidatesDepends On
anti_of_mem_edgeSet πŸ“–β€”SimpleGraph
SimpleGraph.instLE
Sym2
Set
Set.instMembership
SimpleGraph.edgeSet
SimpleGraph.IsBridge
β€”β€”SimpleGraph.isBridge_iff_mem_and_forall_cycle_notMem
SimpleGraph.Walk.IsCycle.mapLe
SimpleGraph.Walk.edges_mapLe_eq_edges

SimpleGraph.Iso

Definitions

NameCategoryTheorems
connectedComponentEquiv πŸ“–CompOp
5 mathmath: connectedComponentEquiv_symm_apply, connectedComponentEquiv_refl, connectedComponentEquiv_trans, connectedComponentEquiv_apply, connectedComponentEquiv_symm

Theorems

NameKindAssumesProvesValidatesDepends On
connectedComponentEquiv_apply πŸ“–mathematicalβ€”DFunLike.coe
Equiv
SimpleGraph.ConnectedComponent
EquivLike.toFunLike
Equiv.instEquivLike
connectedComponentEquiv
SimpleGraph.ConnectedComponent.map
RelEmbedding.toRelHom
SimpleGraph.Adj
RelIso.toRelEmbedding
β€”β€”
connectedComponentEquiv_refl πŸ“–mathematicalβ€”connectedComponentEquiv
refl
Equiv.refl
SimpleGraph.ConnectedComponent
β€”Equiv.Perm.ext
connectedComponentEquiv_symm πŸ“–mathematicalβ€”connectedComponentEquiv
symm
Equiv.symm
SimpleGraph.ConnectedComponent
β€”Equiv.ext
connectedComponentEquiv_symm_apply πŸ“–mathematicalβ€”DFunLike.coe
Equiv
SimpleGraph.ConnectedComponent
EquivLike.toFunLike
Equiv.instEquivLike
Equiv.symm
connectedComponentEquiv
SimpleGraph.ConnectedComponent.map
RelEmbedding.toRelHom
SimpleGraph.Adj
RelIso.toRelEmbedding
symm
β€”β€”
connectedComponentEquiv_trans πŸ“–mathematicalβ€”connectedComponentEquiv
RelIso.trans
SimpleGraph.Adj
Equiv.trans
SimpleGraph.ConnectedComponent
β€”Equiv.ext
connected_iff πŸ“–mathematicalβ€”SimpleGraph.Connectedβ€”SimpleGraph.Connected.map
Equiv.surjective
preconnected_iff πŸ“–mathematicalβ€”SimpleGraph.Preconnectedβ€”SimpleGraph.Preconnected.map
Equiv.surjective
reachable_iff πŸ“–mathematicalβ€”SimpleGraph.Reachable
DFunLike.coe
SimpleGraph.Iso
RelIso.instFunLike
SimpleGraph.Adj
β€”SimpleGraph.Reachable.map
Equiv.left_inv
symm_apply_reachable πŸ“–mathematicalβ€”SimpleGraph.Reachable
DFunLike.coe
SimpleGraph.Iso
RelIso.instFunLike
SimpleGraph.Adj
symm
β€”reachable_iff
RelIso.apply_symm_apply

SimpleGraph.Preconnected

Theorems

NameKindAssumesProvesValidatesDepends On
degree_pos_of_nontrivial πŸ“–mathematicalSimpleGraph.PreconnectedSimpleGraph.degreeβ€”support_eq_univ
exists_adj_of_nontrivial πŸ“–mathematicalSimpleGraph.PreconnectedSimpleGraph.Adjβ€”exists_ne
SimpleGraph.Walk.adj_snd
SimpleGraph.Walk.not_nil_of_ne
exists_isPath πŸ“–mathematicalSimpleGraph.PreconnectedSimpleGraph.Walk.IsPathβ€”SimpleGraph.Reachable.exists_isPath
induce_of_degree_eq_one πŸ“–mathematicalSimpleGraph.Preconnected
Set.Subsingleton
SimpleGraph.neighborSet
Set.Elem
SimpleGraph.induce
β€”exists_isPath
SimpleGraph.Walk.IsTrail.not_mem_support_of_subsingleton_neighborSet
SimpleGraph.Walk.IsPath.isTrail
SimpleGraph.Walk.start_mem_support
SimpleGraph.Walk.end_mem_support
map πŸ“–β€”DFunLike.coe
SimpleGraph.Hom
RelHom.instFunLike
SimpleGraph.Adj
SimpleGraph.Preconnected
β€”β€”Function.Surjective.forallβ‚‚
Nonempty.map
minDegree_pos_of_nontrivial πŸ“–mathematicalSimpleGraph.PreconnectedSimpleGraph.minDegreeβ€”SimpleGraph.exists_minimal_degree_vertex
Nontrivial.to_nonempty
degree_pos_of_nontrivial
mono πŸ“–β€”SimpleGraph
SimpleGraph.instLE
SimpleGraph.Preconnected
β€”β€”SimpleGraph.Reachable.mono
of_subsingleton πŸ“–mathematicalβ€”SimpleGraph.Preconnectedβ€”SimpleGraph.Reachable.of_subsingleton
set_univ_walk_nonempty πŸ“–mathematicalSimpleGraph.PreconnectedSet.Nonempty
SimpleGraph.Walk
Set.univ
β€”Set.nonempty_iff_univ_nonempty
subsingleton_connectedComponent πŸ“–mathematicalSimpleGraph.PreconnectedSimpleGraph.ConnectedComponentβ€”SimpleGraph.ConnectedComponent.indβ‚‚
SimpleGraph.ConnectedComponent.sound
support_eq_univ πŸ“–mathematicalSimpleGraph.PreconnectedSimpleGraph.support
Set.univ
β€”exists_ne

SimpleGraph.Reachable

Theorems

NameKindAssumesProvesValidatesDepends On
elim πŸ“–β€”β€”β€”β€”β€”
elim_path πŸ“–β€”β€”β€”β€”elim
exists_isPath πŸ“–mathematicalβ€”SimpleGraph.Walk.IsPathβ€”SimpleGraph.Path.isPath
map πŸ“–mathematicalβ€”SimpleGraph.Reachable
DFunLike.coe
SimpleGraph.Hom
RelHom.instFunLike
SimpleGraph.Adj
β€”elim
mem_subgraphVerts πŸ“–β€”SimpleGraph.Subgraph.Adj
Set
Set.instMembership
SimpleGraph.Subgraph.verts
β€”β€”β€”
mono πŸ“–mathematicalSimpleGraph
SimpleGraph.instLE
SimpleGraph.Reachableβ€”map
mono' πŸ“–mathematicalSimpleGraph
SimpleGraph.instLE
Pi.hasLe
Prop.le
SimpleGraph.Reachable
β€”mono
of_subsingleton πŸ“–mathematicalβ€”SimpleGraph.Reachableβ€”refl
refl πŸ“–mathematicalβ€”SimpleGraph.Reachableβ€”β€”
rfl πŸ“–mathematicalβ€”SimpleGraph.Reachableβ€”refl
trans πŸ“–mathematicalβ€”SimpleGraph.Reachableβ€”elim

SimpleGraph.Subgraph

Definitions

NameCategoryTheorems
Connected πŸ“–CompData
15 mathmath: top_induce_pair_connected_of_adj, induce_union_connected, SimpleGraph.ConnectedComponent.maximal_connected_toSubgraph, connected_induce_top_sup, connected_sup, connected_iff_forall_exists_walk_subgraph, singletonSubgraph_connected, subgraphOfAdj_connected, connected_iff', SimpleGraph.connected_induce_iff, SimpleGraph.ConnectedComponent.maximal_subgraph_connected_iff, SimpleGraph.Connected.toSubgraph, SimpleGraph.Walk.toSubgraph_connected, connected_iff, SimpleGraph.ConnectedComponent.connected_toSubgraph

SimpleGraph.Walk

Theorems

NameKindAssumesProvesValidatesDepends On
exists_mem_edges_of_not_reachable_deleteEdges πŸ“–mathematicalSimpleGraph.Reachable
SimpleGraph.deleteEdges
Sym2
Set
Set.instMembership
edges
β€”Mathlib.Tactic.Contrapose.contraposeβ‚‚
Mathlib.Tactic.Push.not_and_eq
mem_edges_of_not_reachable_deleteEdges πŸ“–mathematicalSimpleGraph.Reachable
SimpleGraph.deleteEdges
Sym2
Set
Set.instSingletonSet
edgesβ€”exists_mem_edges_of_not_reachable_deleteEdges
reachable πŸ“–mathematicalβ€”SimpleGraph.Reachableβ€”β€”

SimpleGraph.Walk.IsTrail

Theorems

NameKindAssumesProvesValidatesDepends On
not_mem_edges_of_not_reachable πŸ“–mathematicalSimpleGraph.Walk.IsTrail
SimpleGraph.Reachable
SimpleGraph.deleteEdges
Sym2
Set
Set.instSingletonSet
SimpleGraph.Walk.edgesβ€”disjoint_edges_takeUntil_dropUntil
SimpleGraph.Walk.snd_mem_support_of_mem_edges
SimpleGraph.Walk.mem_edges_of_not_reachable_deleteEdges
SimpleGraph.Walk.edges_reverse
not_mem_support_of_not_reachable πŸ“–mathematicalSimpleGraph.Walk.IsTrail
SimpleGraph.Reachable
SimpleGraph.deleteEdges
Sym2
Set
Set.instSingletonSet
SimpleGraph.Walk.supportβ€”not_mem_edges_of_not_reachable
SimpleGraph.Walk.edges_takeUntil_subset
SimpleGraph.Walk.mem_edges_of_not_reachable_deleteEdges
not_mem_support_of_subsingleton_neighborSet πŸ“–mathematicalSimpleGraph.Walk.IsTrail
Set.Subsingleton
SimpleGraph.neighborSet
SimpleGraph.Walk.supportβ€”SimpleGraph.adj_of_mem_walk_support
not_mem_support_of_not_reachable
SimpleGraph.Walk.snd_reverse
SimpleGraph.Walk.adj_snd
SimpleGraph.Walk.not_nil_of_ne

SimpleGraph.reachable_deleteEdges_iff_exists_cycle

Theorems

NameKindAssumesProvesValidatesDepends On
aux πŸ“–β€”Sym2
SimpleGraph.Walk.edges
SimpleGraph.Walk.IsTrail
SimpleGraph.Walk.support
SimpleGraph.Walk.takeUntil
SimpleGraph.Walk.fst_mem_support_of_mem_edges
β€”β€”SimpleGraph.Walk.fst_mem_support_of_mem_edges
SimpleGraph.Walk.take_spec
List.disjoint_of_nodup_append
SimpleGraph.Walk.edges_append
List.nodup_append_comm
SimpleGraph.Walk.isTrail_def
SimpleGraph.Walk.edges_reverse

---

← Back to Index