proposition: Lemma uf_union_unaffected_inhabited: forall (g1 g2 : PreGraph Vertex Edge) a b v (S1 S2 S3 : uf_set), S1 a -> S2 b -> S3 v -> uf_set_in g1 S1 -> uf_set_in g1 S2 -> ~ Same_set S3 S1 -> ~ Same_set S3 S2 -> uf_set_in g1 S3 -> uf_union g1 a b g2 -> exists rt : Vertex, S3 rt /\ (forall x : Vertex, S3 x <-> uf_root g2 x rt).
proof: Proof. intros. apply (uf_union_unaffected_gen _ _ _ _ S1 S2 S3) in H7; trivial. unfold uf_set_in in H7. destruct H7; trivial. exfalso; apply (inhabited_set_nonempty _ _ _ H1 H7). 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