diff --git a/lemon/hypercube_graph.h b/lemon/hypercube_graph.h
--- a/lemon/hypercube_graph.h
+++ b/lemon/hypercube_graph.h
@@ -287,7 +287,8 @@
   /// Two nodes are connected in the graph if and only if their indices
   /// differ only on one position in the binary form.
   /// This class is completely static and it needs constant memory space.
-  /// Thus you can neither add nor delete nodes or edges.
+  /// Thus you can neither add nor delete nodes or edges, however 
+  /// the structure can be resized using resize().
   ///
   /// This type fully conforms to the \ref concepts::Graph "Graph concept".
   /// Most of its member functions and nested classes are documented
@@ -306,6 +307,21 @@
     /// Constructs a hypercube graph with \c dim dimensions.
     HypercubeGraph(int dim) { construct(dim); }
 
+    /// \brief Resizes the graph
+    ///
+    /// This function resizes the graph. It fully destroys and
+    /// rebuilds the structure, therefore the maps of the graph will be
+    /// reallocated automatically and the previous values will be lost.
+    void resize(int dim) {
+      Parent::notifier(Arc()).clear();
+      Parent::notifier(Edge()).clear();
+      Parent::notifier(Node()).clear();
+      construct(dim);
+      Parent::notifier(Node()).build();
+      Parent::notifier(Edge()).build();
+      Parent::notifier(Arc()).build();
+    }
+
     /// \brief The number of dimensions.
     ///
     /// Gives back the number of dimensions.
diff --git a/test/digraph_test.cc b/test/digraph_test.cc
--- a/test/digraph_test.cc
+++ b/test/digraph_test.cc
@@ -378,7 +378,12 @@
 void checkFullDigraph(int num) {
   typedef FullDigraph Digraph;
   DIGRAPH_TYPEDEFS(Digraph);
+
   Digraph G(num);
+  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
+
+  G.resize(num);
+  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
 
   checkGraphNodeList(G, num);
   checkGraphArcList(G, num * num);
diff --git a/test/graph_test.cc b/test/graph_test.cc
--- a/test/graph_test.cc
+++ b/test/graph_test.cc
@@ -270,6 +270,13 @@
   GRAPH_TYPEDEFS(Graph);
 
   Graph G(num);
+  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
+        "Wrong size");
+
+  G.resize(num);
+  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
+        "Wrong size");
+
   checkGraphNodeList(G, num);
   checkGraphEdgeList(G, num * (num - 1) / 2);
 
@@ -414,6 +421,10 @@
   check(G.width() == width, "Wrong column number");
   check(G.height() == height, "Wrong row number");
 
+  G.resize(width, height);
+  check(G.width() == width, "Wrong column number");
+  check(G.height() == height, "Wrong row number");
+
   for (int i = 0; i < width; ++i) {
     for (int j = 0; j < height; ++j) {
       check(G.col(G(i, j)) == i, "Wrong column");
@@ -489,6 +500,11 @@
   GRAPH_TYPEDEFS(HypercubeGraph);
 
   HypercubeGraph G(dim);
+  check(G.dimension() == dim, "Wrong dimension");
+
+  G.resize(dim);
+  check(G.dimension() == dim, "Wrong dimension");
+  
   checkGraphNodeList(G, 1 << dim);
   checkGraphEdgeList(G, dim * (1 << (dim-1)));
   checkGraphArcList(G, dim * (1 << dim));