Goal:
  
  G1 : t
  G2 : t
  l : labelling
  Gl := relabel_on G1 G2 l : t
  H : invariants G1
  preserves_edges : forall e : EdgeSet.elt,
                    EdgeSet.In e (E G1) -> EdgeSet.In e (E G2)
  HGl : correct_labelling G1 l
  H0 : invariants G2
  H1 : acyclic_no_loop G2
  embed : forall v1 v2 : VSet.elt,
          VSet.In v1 (V G1) ->
          VSet.In v2 (V G1) -> (lsp G2 v1 v2 <= lsp G1 v1 v2)%nbar
  G : t
  s0 : VSet.t
  s' : VSet.t
  x : V.t
  y : V.t
  z : V.t
  d : DisjointAdd x s0 s'
  e : EdgeOf G x y
  a0 : SPath G s0 y z
  IHa0 : Acc
           (fun
              x
               y : sigma
                     (fun
                        index : sigma
                                  (fun _ : VSet.t =>
                                   sigma (fun _ : V.t => V.t)) =>
                      SPath G (pr1 index) (pr1 (pr2 index)) (pr2 (pr2 index)))
            =>
            SPath_direct_subterm G (pr1 (pr1 x)) (pr1 (pr2 (pr1 x)))
              (pr2 (pr2 (pr1 x))) (pr1 (pr1 y)) (pr1 (pr2 (pr1 y)))
              (pr2 (pr2 (pr1 y))) (pr2 x) (pr2 y))
           {|
             pr1 := {| pr1 := s0; pr2 := {| pr1 := y; pr2 := z |} |};
             pr2 := a0
           |}
  pr1 : VSet.t
  pr0 : V.t
  pr2 : V.t
  y1 : SPath G pr1 pr0 pr2
  H2 : SPath_direct_subterm G pr1 pr0 pr2 s' x z y1
         (spath_step G s0 s' x y z d e a0)
  H3 := {|
          pr1 :=
            {|
              pr1 := pr1;
              pr2 :=
                {|
                  pr1 := pr0;
                  pr2 :=
                    {|
                      pr1 := pr2;
                      pr2 :=
                        {|
                          pr1 := s';
                          pr2 :=
                            {|
                              pr1 := x;
                              pr2 :=
                                {|
                                  pr1 := z;
                                  pr2 :=
                                    {|
                                      pr1 := y1;
                                      pr2 := spath_step G s0 s' x y z d e a0
                                    |}
                                |}
                            |}
                        |}
                    |}
                |}
            |};
          pr2 := H2
        |}
     : sigma
         (fun
            index : sigma
                      (fun H : VSet.t =>
                       sigma
                         (fun H0 : V.t =>
                          sigma
                            (fun H1 : V.t =>
                             sigma
                               (fun H2 : VSet.t =>
                                sigma
                                  (fun H3 : V.t =>
                                   sigma
                                     (fun H4 : V.t =>
                                      sigma
                                        (fun _ : SPath G H H0 H1 =>
                                         SPath G H2 H3 H4))))))) =>
          SPath_direct_subterm G (Init.pr1 index) 
            (Init.pr1 (Init.pr2 index))
            (Init.pr1 (Init.pr2 (Init.pr2 index)))
            (Init.pr1 (Init.pr2 (Init.pr2 (Init.pr2 index))))
            (Init.pr1 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index)))))
            (Init.pr1
               (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index))))))
            (Init.pr1
               (Init.pr2
                  (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index)))))))
            (Init.pr2
               (Init.pr2
                  (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index))))))))
  H4 := {|
          pr1 := pr1;
          pr2 :=
            {|
              pr1 := pr0;
              pr2 :=
                {|
                  pr1 := pr2;
                  pr2 :=
                    {|
                      pr1 := s';
                      pr2 :=
                        {|
                          pr1 := x;
                          pr2 :=
                            {|
                              pr1 := z;
                              pr2 :=
                                {|
                                  pr1 := y1;
                                  pr2 := spath_step G s0 s' x y z d e a0
                                |}
                            |}
                        |}
                    |}
                |}
            |}
        |}
     : sigma
         (fun H : VSet.t =>
          sigma
            (fun H0 : V.t =>
             sigma
               (fun H1 : V.t =>
                sigma
                  (fun H2 : VSet.t =>
                   sigma
                     (fun H3 : V.t =>
                      sigma
                        (fun H4 : V.t =>
                         sigma (fun _ : SPath G H H0 H1 => SPath G H2 H3 H4)))))))
  H5 := H2
     : (fun
          index : sigma
                    (fun H : VSet.t =>
                     sigma
                       (fun H0 : V.t =>
                        sigma
                          (fun H1 : V.t =>
                           sigma
                             (fun H2 : VSet.t =>
                              sigma
                                (fun H3 : V.t =>
                                 sigma
                                   (fun H4 : V.t =>
                                    sigma
                                      (fun _ : SPath G H H0 H1 =>
                                       SPath G H2 H3 H4))))))) =>
        SPath_direct_subterm G (Init.pr1 index) (Init.pr1 (Init.pr2 index))
          (Init.pr1 (Init.pr2 (Init.pr2 index)))
          (Init.pr1 (Init.pr2 (Init.pr2 (Init.pr2 index))))
          (Init.pr1 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index)))))
          (Init.pr1
             (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index))))))
          (Init.pr1
             (Init.pr2
                (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index)))))))
          (Init.pr2
             (Init.pr2
                (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 (Init.pr2 index))))))))
         H4
  ============================
   (let H := CoreTactics.block in
    let H0 := CoreTactics.block in
    Acc
      (fun
         x
          y : sigma
                (fun
                   index : sigma
                             (fun _ : VSet.t => sigma (fun _ : V.t => V.t))
                 =>
                 SPath G (Init.pr1 index) (Init.pr1 (Init.pr2 index))
                   (Init.pr2 (Init.pr2 index))) =>
       SPath_direct_subterm G (Init.pr1 (Init.pr1 x))
         (Init.pr1 (Init.pr2 (Init.pr1 x)))
         (Init.pr2 (Init.pr2 (Init.pr1 x))) (Init.pr1 (Init.pr1 y))
         (Init.pr1 (Init.pr2 (Init.pr1 y)))
         (Init.pr2 (Init.pr2 (Init.pr1 y))) (Init.pr2 x) 
         (Init.pr2 y))
      {|
        pr1 := {| pr1 := pr1; pr2 := {| pr1 := pr0; pr2 := pr2 |} |};
        pr2 := y1
      |})


DEBUG:Going to execute:
generalize (eq_refl : t = id'1); clearbody id'2 id'1; clear id' id;
            try unfold signature in id'2; hnf in id'2; 
            simpl in id'2