diff --git a/lemon/edge_set.h b/lemon/edge_set.h
--- a/lemon/edge_set.h
+++ b/lemon/edge_set.h
@@ -84,6 +84,12 @@
 
     ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Arc addArc(const Node& u, const Node& v) {
       int n;
       if (first_free_arc == -1) {
@@ -416,6 +422,12 @@
 
     ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Edge addEdge(const Node& u, const Node& v) {
       int n;
 
@@ -816,6 +828,12 @@
 
     SmartArcSetBase() {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Arc addArc(const Node& u, const Node& v) {
       int n = arcs.size();
       arcs.push_back(ArcT());
@@ -1112,6 +1130,12 @@
 
     SmartEdgeSetBase() {}
 
+    Node addNode() {
+      LEMON_ASSERT(false,
+        "This graph structure does not support node insertion");
+      return INVALID; // avoid warning
+    }
+
     Edge addEdge(const Node& u, const Node& v) {
       int n = arcs.size();
       arcs.push_back(ArcT());