proposition: Lemma mark1_mark_left_mark_right: forall (g1 g2 g3 g4: Graph) root l r, vvalid g1 root -> vgamma g1 root = (false, l, r) -> mark1 root g1 g2 -> mark l g2 g3 -> mark r g3 g4 -> mark root g1 g4.
proof: Proof. intros. apply (mark1_mark_list_mark root (l :: r :: nil)); auto. + intros; simpl. inversion H0. unfold Complement, Ensembles.In. rewrite H5; congruence. + hnf; intros. apply gamma_step with (y := n') in H0; auto. rewrite H0; simpl. pose proof eq_sym_iff n' l. pose proof eq_sym_iff n' r. tauto. + split_relation_list ((lg_gg g2) :: nil); eauto. unfold mark_list. simpl map. split_relation_list ((lg_gg g3) :: nil); eauto. Qed.
imports: CertiGraph.lib.Ensembles_ext Coq.Lists.List VST.msl.seplog VST.msl.log_normalize VST.msl.Coqlib2 CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext CertiGraph.lib.relation_list CertiGraph.msl_ext.log_normalize CertiGraph.msl_ext.iter_sepcon CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.reachable_computable CertiGraph.graph.reachable_ind CertiGraph.graph.subgraph2 CertiGraph.graph.graph_gen CertiGraph.graph.dag CertiGraph.graph.weak_mark_lemmas CertiGraph.msl_application.Graph CertiGraph.msl_application.Graph_Mark CertiGraph.msl_application.GraphBin Coq.Logic.Classical