proposition: Lemma uf_union_affected_inhabited: forall (g1 g2 : PreGraph Vertex Edge) (a b : Vertex) (S1 S2 : uf_set), S1 a -> S2 b -> uf_set_in g1 S1 -> uf_set_in g1 S2 -> uf_union g1 a b g2 -> exists rt : Vertex, Ensembles.Union Vertex S1 S2 rt /\ (forall x : Vertex, Ensembles.Union Vertex S1 S2 x <-> uf_root g2 x rt).
proof: Proof. intros. apply (uf_union_affected_gen _ _ _ _ S1 S2) in H3; trivial. destruct H3; trivial. exfalso. apply (inhabited_set_nonempty _ (Ensembles.Union Vertex S1 S2) a); trivial. apply Union_introl; trivial. Qed.
imports: CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext CertiGraph.lib.List_ext CertiGraph.lib.Ensembles_ext CertiGraph.lib.EnumEnsembles CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.graph_gen CertiGraph.graph.MathGraph CertiGraph.graph.LstGraph CertiGraph.graph.FiniteGraph CertiGraph.graph.reachable_computable