Trying to build all existing paths for an udirected graph defined as a map of edges using the following algorithm:

Start: with a given vertice A 
Find an edge (X.A, X.B) or (X.B, X.A), add this edge to path
Find all edges Ys fpr which either (Y.C, Y.B) or (Y.B, Y.C) is true 
For each Ys: A=B, goto Start

Providing edges are defined as the following map, where keys are tuples consisting of two vertices:

    val edges = Map(
      ("n1", "n2") -> "n1n2",
      ("n1", "n3") -> "n1n3",
      ("n3", "n4") -> "n3n4",
      ("n5", "n1") -> "n5n1",
      ("n5", "n4") -> "n5n4")

As an output I need to get a list of ALL pathes where each path is a list of adjecent edges like this:

  val allPaths = List(
    List(("n1", "n2") -> "n1n2"),
    List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"),
    List(("n5", "n1") -> "n5n1"),
    List(("n5", "n4") -> "n5n4"),
    List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4"))
    //...
    //... more pathes to go
}

Note: Edge XY = (x,y) -> "xy" and YX = (y,x) -> "yx" exist as one instance only, either as XY or YX

So far I have managed to implement code that duplicates edges in the path, which is wrong and I can not find the error:

object Graph2 {
  type Vertice = String
  type Edge = ((String, String), String)
  type Path = List[((String, String), String)]

  val edges = Map(
    //(("v1", "v2") , "v1v2"),
    (("v1", "v3") , "v1v3"),
    (("v3", "v4") , "v3v4")
    //(("v5", "v1") , "v5v1"),
    //(("v5", "v4") , "v5v4")
    )

  def main(args: Array[String]): Unit = {

    val processedVerticies: Map[Vertice, Vertice] = Map()
    val processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)] = Map()
    val path: Path = List()
    println(buildPath(path, "v1", processedVerticies, processedEdges))

  }

  /**
   * Builds path from connected by edges vertices starting from given vertice
   * Input: map of edges
   * Output: list of connected edges like:
   List(("n1", "n2") -> "n1n2"),
    List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"),
    List(("n5", "n1") -> "n5n1"),
    List(("n5", "n4") -> "n5n4"),
    List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4"))
   */
  def buildPath(path: Path,
    vertice: Vertice,
    processedVerticies: Map[Vertice, Vertice],
    processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)]): List[Path] = {
    println("V: " + vertice + " VM:  " + processedVerticies + " EM: " + processedEdges)
    if (!processedVerticies.contains(vertice)) {
      val edges = children(vertice)
      println("Edges: " + edges)
      val x = edges.map(edge => {
        if (!processedEdges.contains(edge._1)) {
          addToPath(vertice, processedVerticies.++(Map(vertice -> vertice)), processedEdges, path, edge)
        } else {
          println("ALready have edge: "+edge+" Return path:"+path)
          path
        }
      })
      val y = x.toList
      y
    } else {
      List(path)
    }
  }

  def addToPath(
    vertice: Vertice,
    processedVerticies: Map[Vertice, Vertice],
    processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)],
    path: Path,
    edge: Edge): Path = {

    val newPath: Path = path ::: List(edge)
    val key = edge._1
    val nextVertice = neighbor(vertice, key)

    val x = buildPath (newPath, 
             nextVertice, 
             processedVerticies, 
             processedEdges ++ (Map((vertice, nextVertice) -> (vertice, nextVertice)))
          ).flatten // need define buidPath type 
    x
  }

  def children(vertice: Vertice) = {
    edges.filter(p => (p._1)._1 == vertice || (p._1)._2 == vertice)
  }

  def containsPair(x: (Vertice, Vertice), m: Map[(Vertice, Vertice), (Vertice, Vertice)]): Boolean = {
    m.contains((x._1, x._2)) || m.contains((x._2, x._1))
  }

  def neighbor(vertice: String, key: (String, String)): String = key match {
    case (`vertice`, x) => x
    case (x, `vertice`) => x
  }

}  

Running this results in:

List(List(((v1,v3),v1v3), ((v1,v3),v1v3), ((v3,v4),v3v4)))

Why is that?