Immutable data structures with path-dependent types in Scala

Question

I've written an implementation of a directed graph in Scala, which uses path dependent types to enforce the invariant that edges may only be created between nodes of the same graph:

package uk.co.timcowlishaw.BayTree;
import scala.collection.IndexedSeq;
import scala.collection.immutable.Vector;

sealed trait Graph[T] {
  type Self
  def addVertex(value : T) : Vertex[T, Self];
  def addEdge(source : Vertex[T, Self], destination : Vertex[T, Self]) : Edge[T, Self];
}


sealed trait Vertex[T, G] {
  def value : T;
}

sealed trait Edge[T, G] {
  def source : Vertex[T, G];
  def destination : Vertex[T, G];
}


object Graph {

  type TwoDimensional[M[_], X] = M[M[X]];

  type AdjacencyMatrix = TwoDimensional[IndexedSeq, Boolean];

  def apply[T] : Graph[T] = new GraphImpl[T]();

  private case class GraphImpl[T] extends Graph[T] {
    type Self = this.type

    private case class VertexImpl(val value : T) extends Vertex[T, Self]

    private case class EdgeImpl(
      val source : Vertex[T, Self],
      val destination : Vertex[T, Self]
    ) extends Edge[T, Self]

    private var vertices = Vector[VertexImpl]()
    private var adjacency = Vector.fill(0,0)(false)

    def addVertex(value : T) : Vertex[T, Self] = {
      val vertex = VertexImpl(value)
      vertices = vertices :+ vertex
      adjacency = adjacency.map(_ :+ false) :+ Vector.fill(vertices.length)(false)
      return vertex
    }

    def addEdge(source : Vertex[T, Self], destination : Vertex[T, Self]) : Edge[T, Self] = {
      val edge = EdgeImpl(source, destination)
      val adj = adjacency(vertices.indexOf(source))
      adjacency = adjacency.updated(vertices.indexOf(source), adj.updated(vertices.indexOf(destination), true))
      return edge
    }
  }
}

The instances of GraphImpl here are mutable, as adding a new node or edge mutates the vertex list and/or the adjacency matrix.

I'd like to adapt this to produce an immutable implementation. As far as I can see, this would involve adapting the addVertex and addEdge methods of the Graph trait to return a tuple (Graph, Vertex) or (Graph, Edge) where the first element of the tuple is the updated Graph object. However, trying to specify this return type, I run into problems:

sealed trait Graph[T] {
  type Self
  def addVertex(value : T) : (Graph[T], Vertex[T, ???]);
  def addEdge(source : Vertex[T, Self], destination : Vertex[T, Self]) : (Graph[T], Edge[T, ???]);
}

Fairly obviously, the second type parameter of the returned Vertex or Edge should be the Self member of the returned Graph (and not the Self member of the target of the method call). I can't for the life of me work out how to express this in the type signature (as I don't have a reference to the returned graph in order to express this type). Can anyone think of a way to express this, or, failing that, another way to enforce the same invariants at compile time for an immutable Graph type?

Many thanks.