# Counting triangles in a graph by iteratively removing high-degree nodes

Computing `nx.triangles(G)` on an undirected graph with about 150 thousand nodes and 2 million edges, is currently very slow (on the scale of 80 hours). If the node degree distribution is highly skewed, is there any problem with counting triangles using the following procedure?

``````import networkx as nx

def largest_degree_node(G):
return sorted(G.degree(), key=lambda x: x[1])[-1][0]

def count_triangles(G):
G=G.copy()
triangle_counts = 0
while len(G.nodes()):
focal_node = largest_degree_node(G)
triangle_counts += nx.triangles(G, nodes=[focal_node])[focal_node]
G.remove_node(focal_node)
return triangle_counts

G = nx.erdos_renyi_graph(1000, 0.1)

# compute triangles with nx
triangles_nx = int(sum(v for k, v in nx.triangles(G).items()) / 3)

# compute triangles iteratively
triangles_iterative = count_triangles(G)

# assertion passes
assert int(triangles_nx) == int(triangles_iterative)
``````

The assertion passes, but I am wary that there are some edge cases where this iterative approach will not work.