proposition: Lemma spanning_tree_not_edge_derive: forall (g1 : Graph) (root : V) (P : V -> Prop) (g2 : Graph) (x y : V), spanning_tree g1 root P g2 -> ~ g1 |= root ~o~> x satisfying P -> g2 |= x ~> y -> g1 |= x ~> y.
proof: Proof. intros. destruct H1 as [? [? ?]]. hnf. split; [|split]; [rewrite spanning_tree_vvalid_s; eauto ..|]. rewrite step_spec in H3 |-* . destruct H3 as [e [? [? ?]]]. destruct H as [? _]. hnf in H. simpl in H. unfold predicate_weak_evalid in H. destruct H as [_ [? [? ?]]]. specialize (H e). specialize (H6 e). specialize (H7 e). rewrite <- H4 in *. assert (evalid g2 e /\ ~ g1 |= root ~o~> src g2 e satisfying P) by intuition. subst y. exists e. intuition. Qed.
imports: Coq.Classes.Morphisms CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext CertiGraph.lib.EnumEnsembles CertiGraph.lib.List_ext CertiGraph.lib.relation_list CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.graph_gen CertiGraph.graph.graph_relation CertiGraph.graph.subgraph2 CertiGraph.graph.reachable_ind Coq.Logic.Classical