Could some one explain why this does not work and how to make it work? Thanks!

Welcome to Scala 2.12.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_45).
Type in expressions for evaluation. Or try :help.
scala> trait Graph { type Node; def nodes: Seq[Set[Node]] }
defined trait Graph
scala> case class GraphWrap[G <: Graph](graph: G) { def nodesReversed: Seq[Set[G#Node]] = graph.nodes.reverse }
<console>:12: error: type mismatch;
found : Seq[Set[GraphWrap.this.graph.Node]]
required: Seq[Set[G#Node]]
case class GraphWrap[G <: Graph](graph: G) { def nodesReversed: Seq[Set[G#Node]] = graph.nodes.reverse }
^
scala>

Since G is not known to be a singleton type, the second bullet point of Â§3.5.1 â€śEquivalenceâ€ť does not apply:

If a path p has a singleton type q.type, then p.type â‰ˇ q.type.

Because this cannot be satisfied, graph.type â‰˘ G, and so graph.type#Node â‰˘ G#Node, graph.type#Node meaning graph.Node.

While it is true that graph.Node <: G#Node, since it occurs within the invariant position Î»[Î±] = Seq[Set[Î±]], that conformance is insufficient to satisfy the expected type.

As for fixing it? One way would be

case class GraphWrap[G <: Graph, N](graph: G {type Node = N}) { def nodesReversed: Seq[Set[N]] = graph.nodes.reverse }
// tested with your example in 2.12.4

That works if graph is a public val in your original code, just as it is in your example. Its interface equivalence to what you originally declared is described in â€śRelatable variablesâ€ť in one of the aforementioned posts. In other words, it works out when the caller knows that G is a singleton type, which is common.