proposition: Lemma totally_unmarked_parent_ST_reachable_eq: forall (g1 g2: Graph) x l r, vvalid g1 x -> vgamma g1 x = (true, l, r) -> totally_unmarked g1 l -> spanning_tree g1 l g2 -> vertices_at (reachable g1 x) g2 = reachable_vertices_at x g2.
proof: Proof. intros. apply vertices_at_Same_set. rewrite Same_set_spec. hnf. assert (l = dst (lg_gg g1) (x, L)) by (simpl in H0; inversion H0; auto). apply spanning_tree_totally_unmarked_parent_reachable with (e := (x, L)); auto; try rewrite <- H3; auto. - hnf. split. + apply (@left_valid _ _ _ _ _ _ g1 (binGraph g1)); auto. + apply (@left_sound _ _ _ _ _ _ g1 (binGraph g1) x); auto. - apply vgamma_is_true in H0. auto. - intros; apply Graph_reachable_by_dec, weak_valid_vvalid_dec; right; auto. Qed.
imports: VST.msl.seplog VST.msl.log_normalize CertiGraph.lib.Coqlib CertiGraph.lib.Ensembles_ext CertiGraph.lib.EquivDec_ext Coq.Lists.List CertiGraph.msl_ext.ramification_lemmas CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.graph_gen CertiGraph.graph.graph_relation CertiGraph.graph.subgraph2 CertiGraph.graph.reachable_ind CertiGraph.graph.spanning_tree CertiGraph.graph.BinGraph CertiGraph.graph.MathGraph CertiGraph.graph.FiniteGraph CertiGraph.msl_application.Graph CertiGraph.msl_application.GraphBin CertiGraph.msl_application.GraphBin_Mark