Answer to a question I asked on the Rust forums: https://users.rust-lang.org/t/can-rust-lifetimes-be-used-to-enforce-this-api-rule/4287/3

graph.rs

use std::marker::PhantomData;
use std::collections::HashSet;

type GraphId<'a> = PhantomData<::std::cell::Cell<&'a mut ()>>;

struct Graph<'a> {
    id: GraphId<'a>,
    vertices: usize,
    edges: HashSet<(usize, usize)>
}

struct VertexRef<'a> {
    graph_id: GraphId<'a>,
    index: usize
}

fn with_graph<F, O>(f: F) -> O
    where F: for<'a> FnOnce(Graph<'a>) -> O
{
    f(Graph {id: PhantomData, vertices: 0, edges: HashSet::new()})
}

impl<'a> Graph<'a> {
    fn new_vertex(&mut self) -> VertexRef<'a> {
        let n = self.vertices;
        self.vertices += 1;
        VertexRef { graph_id: self.id, index: n }
    }
    fn add_edge(&mut self, u: VertexRef<'a>, v: VertexRef<'a>) {
        self.edges.insert((u.index, v.index));
    }
}

fn main() {
    with_graph(|mut g1| {
        with_graph(|mut g2| {
            let v1 = g1.new_vertex();  // error: cannot infer an appropriate lifetime parameter `'a` due to conflicting requirements
            let v2 = g2.new_vertex();
            g2.add_edge(v1, v2);
        })
    });
}