Index: trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java
===================================================================
--- trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java	(revision 15554)
+++ trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java	(revision 15555)
@@ -124,5 +124,5 @@
         // try to build a new way which includes all the combined ways
         NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
-        List<Node> path = graph.buildSpanningPath();
+        List<Node> path = graph.buildSpanningPathNoRemove();
         if (path == null) {
             warnCombiningImpossible();
Index: trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java	(revision 15554)
+++ trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java	(revision 15555)
@@ -139,4 +139,6 @@
     private final Set<NodePair> edges;
     private int numUndirectedEges;
+    /** counts the number of edges that were added */
+    private int addedEdges;
     private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
     private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
@@ -195,7 +197,6 @@
      */
     public void add(NodePair pair) {
-        if (!edges.contains(pair)) {
-            edges.add(pair);
-        }
+        addedEdges++;
+        edges.add(pair);
     }
 
@@ -290,5 +291,5 @@
     public List<Node> buildSpanningPath() {
         prepare();
-        if(numUndirectedEges > 0 && isConnected()) {
+        if (numUndirectedEges > 0 && isConnected()) {
             // try to find a path from each "terminal node", i.e. from a
             // node which is connected by exactly one undirected edges (or
@@ -311,4 +312,19 @@
 
     /**
+     * Tries to find a path through the graph which visits each edge (i.e.
+     * the segment of a way) exactly once. If the graph was build from overlapping
+     * ways duplicate edges were removed already. This method will return null if
+     * any duplicated edge was removed.
+     *
+     * @return the path; null, if no path was found or duplicated edges were found
+     * @since xxx
+     */
+    public List<Node> buildSpanningPathNoRemove() {
+        if (edges.size() != addedEdges)
+            return null;
+        return buildSpanningPath();
+    }
+
+    /**
      * Find out if the graph is connected.
      * @return true if it is connected.
@@ -321,5 +337,5 @@
         HashSet<Node> visited = new HashSet<>();
         toVisit.add(nodes.iterator().next());
-        while(!toVisit.isEmpty()) {
+        while (!toVisit.isEmpty()) {
             Node n = toVisit.pop();
             if (!visited.contains(n)) {