I'm not saying it's normal, but if you want to make the example compile you need provide explicit type parameters when instantiating Graph:

g := New(*Vertex, *FromTo)([]*Vertex{}) // ok

Also, while I understand the error message for:

g := New(Vertex, *FromTo)([]*Vertex{}) // error: *Vertex does not satisfy NodeConstraint(Edge) (missing method Edges)

I'm not sure I understand why it says the same thing in the following case, since the Vertex type parameter is now correct:

g := New(*Vertex, FromTo)([]*Vertex{}) // error: Vertex does not satisfy NodeConstraint(Edge) (missing method Edges)

Or maybe is it because there's a mismatch for the 1st type parameter, between Vertex (inferred from FromTo) and *Vertex?

OK, but maybe it is possible to deduce the Edge type as *FromTo from the New([]*Vertex{}) call, for *Vertex has a Edges() []*FromTo method.

This seems like a question which has been answered.