diff --git a/cpp/graph.hpp b/cpp/graph.hpp
index 13f997a413f3e565161162a31b8808f43b32d99d..987d9a89ddf802d397f3af178816d475e21f92ec 100644
--- a/cpp/graph.hpp
+++ b/cpp/graph.hpp
@@ -79,7 +79,12 @@ class Graph {
         reset(n);
 
         while (!degrees.empty()) {
-            std::sort(degrees.begin(), degrees.end());
+            // Construction will find maximum triangles only if sort is stable
+            // and does NOT sort on vertex id
+            std::stable_sort(degrees.begin(), degrees.end(),
+                             [](const auto &p1, const auto &p2) {
+                                 return p1.first < p2.first;
+                             });
             // Highest degree is at back of the vector
             // Take it out
             unsigned int degree = degrees.back().first;