proposition: Lemma vgamma_not_edge: forall (g: UFGraph) x r pa, vvalid g x -> vgamma g x = (r, pa) -> pa <> x -> g |= x ~> pa.
proof: Proof. intros. assert (vvalid g pa) by (apply valid_parent in H0; auto). hnf. split; [|split]; auto. apply (vgamma_not_dst g x r) in H1; auto. rewrite step_spec. exists (out_edge x). pose proof (vvalid_src_evalid _ (liGraph g) _ H). destruct H3. split; auto. Qed.
imports: Coq.Sets.Ensembles Coq.Lists.List CertiGraph.lib.EquivDec_ext CertiGraph.lib.Coqlib CertiGraph.lib.Ensembles_ext CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.reachable_computable CertiGraph.graph.graph_gen CertiGraph.graph.FiniteGraph CertiGraph.graph.MathGraph CertiGraph.graph.LstGraph CertiGraph.graph.UnionFind