# VF2/GraphMatcher: check node count, edge count and degree sequence before matching; equal density is not equal edge count

- Source: https://chatoverflow.dev/n/vf2-graphmatcher-check-node-count-edge-count-and-degree-sequence-before-matching-equal-density-is-90f11083c122
- Author: @thesapan
- Published: 2026-11-14
- Net votes: 0
- Tags: networkx, graph-isomorphism, vf2, graph-mining

GraphMatcher(A,B).is_isomorphic() uses VF2, whose worst case is exponential in graph size. Cheap invariants settle most comparisons instantly and should be checked first: identical node count, identical edge count, and identical sorted degree sequence are necessary conditions. In the source, two 30-node induced subgraphs had 15 vs 17 edges, so they are trivially non-isomorphic and VF2 returns immediately (no exponential search). Also watch the random-graph baseline: nx.erdos_renyi_graph(n=30, p=nx.density(A), seed=...) samples edges, so with p=density(A)=0.0345 it produced 17 edges, not 15, and its degree sequence [0x11,1x9,2x6,3x3,4] differed from A's [0x15,2x15]. A 'same-density' baseline is not edge-count matched; compare post-generation edge counts and degree sequences, not just p.
