Paths with unique relationships

By default Cypher® does not allow the same relationship to be traversed more than once in a given MATCH result, regardless of the direction it is traversed in. The same restriction does not hold for nodes, which may be re-traversed any number of times in a matched path.

Cypher’s default pattern matching behavior can be explicitly specified using the DIFFERENT RELATIONSHIPS keyword (released in Neo4j 2025.06 and only available in Cypher 25) after MATCH. Specifying DIFFERENT RELATIONSHIPS does not alter how a graph pattern is matched. For example: MATCH DIFFERENT RELATIONSHIPS p = (start)--{,2}(end) is functionally equivalent to MATCH p = (start)--{,2}(end).

DIFFERENT RELATIONSHIPS is a GQL conformant match mode. Match modes determine whether relationships can appear more than once in a graph pattern match. For more information, see Syntax and semantics → Match modes.

Example graph

To explain Cypher’s default behavior, which allows for the re-traversal of nodes but not relationships in the same MATCH result, this page will use the scenario of the Seven bridges of Königsberg, a problem studied by Leonhard Euler in 1736 to determine if one could cross all seven bridges of Königsberg exactly once in a single walk.

Graph showing the seven bridges of Königsberg

To recreate the graph, run the following query against an empty Neo4j database:

CREATE (kneiphof:Location {name: "Kneiphof"}),
       (northBank:Location {name: "North Bank"}),
       (southBank:Location {name: "South Bank"}),
       (lomse:Location {name: "Lomse"}),

       (kneiphof)-[:BRIDGE {id: 1}]->(northBank),
       (kneiphof)-[:BRIDGE {id: 6}]->(southBank),
       (kneiphof)-[:BRIDGE {id: 7}]->(lomse),
       (northBank)-[:BRIDGE {id: 5}]->(kneiphof),
       (northBank)-[:BRIDGE {id: 2}]->(lomse),
       (southBank)-[:BRIDGE {id: 4}]->(kneiphof),
       (southBank)-[:BRIDGE {id: 3}]->(lomse)

Cypher’s default traversal rules and the Königsberg bridges problem

Cypher’s default MATCH behavior is ideal to showcase the Königsberg bridges problem: in the graph model, not traversing a relationship means not traversing a bridge, the problem’s key constraint.

Consider the following query, which uses a quantified relationship to search for paths exactly 5 hops away from the start Location node, Kneiphof. The relationships used in this query are directional, meaning paths are traversed following specific directions for each bridge (-[:BRIDGE]->).

Find paths with a length of 5 relationships from a start node
MATCH p = (:Location {name: 'Kneiphof'})-[:BRIDGE]->{5}()
RETURN [n IN nodes(p) | n.name] AS locations,
       [r IN relationships(p) | r.id] AS crossedBridges (1)
1 The list comprehensions iterate over nodes and relationships in a path and return specific properties (the name property from nodes, and the id property from relationships).

As the results show, a node may be traversed several times in the same path, but a relationship (bridge) is never re-traversed (for example, the path [6, 4, 1, 5, 6], which traverses the same bridge more than once, cannot be matched using the DIFFERENT RELATIONSHIPS match mode).

Result
locations crossedBridges

["Kneiphof", "North Bank", "Kneiphof", "South Bank", "Kneiphof", "Lomse"]

[1, 5, 6, 4, 7]

["Kneiphof", "South Bank", "Kneiphof", "North Bank", "Kneiphof", "Lomse"]

[6, 4, 1, 5, 7]

Rows: 2

In the next example, the direction is removed from the pattern, and the path length is increased to 6. It shows that there are 48 valid paths with this length, where no relationships (bridges) are re-traversed. The query returns one of those paths as a samplePath, showing both the nodes and relationships traversed therein.

Find paths with a length of 6 relationships from a start node
MATCH p = (:Location {name: 'Kneiphof'})-[:BRIDGE]-{6}()
WITH count(p) AS pathCount, collect(p)[0] AS samplePath (1)
ORDER BY pathCount
RETURN pathCount,
       [n IN nodes(samplePath) | n.name] AS samplePathLocations,
       [r IN relationships(samplePath) | r.id] AS samplePathBridges
1 The collect() function collects all paths and [0] takes the first entry as the samplePath.
Result
pathCount samplePathLocations samplePathBridges

48

["Kneiphof", "North Bank", "Kneiphof", "South Bank", "Kneiphof", "Lomse", "North Bank"]

[1, 5, 6, 4, 7, 2]

Rows: 1
Graph showing all but one of the seven bridges of Königsberg traversed

In the samplePath with a length of 6 returned by DIFFERENT RELATIONSHIPS, all bridges are traversed except for bridge 3.

However, if the relationship count is increased to 7, 0 paths are returned.

Find paths with a length of 7 relationships
MATCH p = (:Location {name: 'Kneiphof'})--{7}()
RETURN count(p) AS pathCount
Result
pathCount

0

Rows: 1

Using Cypher’s default MATCH behavior, each step must use a unique bridge. After the first step, one bridge is used, leaving six remaining bridges to be used in the subsequent steps. After the sixth bridge is traversed, a seventh step would require re-traversing a bridge, which is not allowed.

This reflects the conclusion of Euler’s Seven bridges of Königsberg problem: the impossibility of crossing each bridge exactly once in a single walk.

For more information about Cypher’s default MATCH behavior, see Syntax & semantics → Match modes.

Non-default MATCH behavior

Cypher’s default MATCH behavior is applicable to most use cases. It is, however, possible to alter how paths are traversed to solve specific problems, either by permitting re-traversal of relationships using REPEATABLE ELEMENTS or by not allowing the re-traversal of nodes in the same path with the ACYCLIC keyword.

For more information, see: