Does VF2++ require identical vertex identifiers?

No. Isomorphism allows a consistent renaming.

Does the NetworkX Boolean interface compare node attributes by default?

No. Its documented default omits node-attribute comparison unless a label attribute is selected.

Can there be several valid mappings?

Yes. Graph symmetries can produce multiple isomorphisms.

AI Glossary / Graphs and symbolic AI / Intermediate

VF2++

Definition

VF2++ is an algorithm for testing graph isomorphism: whether two graphs have the same structure after consistently renaming their vertices. It searches for a one-to-one vertex mapping that preserves the relevant connections and, when requested, node labels. It improves the organization and pruning of the VF2 search family rather than treating matching vertex counts as sufficient evidence of equivalence.

What it means

Two drawings can look different while representing the same graph. Conversely, two graphs can have the same number of vertices, edges, and vertex degrees without being isomorphic. The question is whether one complete correspondence preserves the structure everywhere.
The required notion of sameness must be explicit. Plain structural isomorphism ignores descriptive node attributes. Label-aware isomorphism also requires the selected labels to agree. In an application, that difference can determine whether a mapping respects component roles or merely matches an unlabeled connection pattern. An algorithm's name does not imply that every attribute is checked automatically.

How it works

The search incrementally constructs a mapping between vertices and rejects candidate pairings that cannot lead to an isomorphism. VF2++ uses information such as vertex degree and label rarity to order difficult choices earlier, together with feasibility checks that prune incompatible branches.
Its NetworkX implementation uses a nonrecursive search structure. The Boolean interface reports whether a mapping exists; related interfaces can provide a mapping or enumerate mappings. Node-label matching is controlled by an explicit attribute setting, with a default value for missing labels. Exact behavior and supported graph types should be checked against the interface being used. Faster pruning does not make every graph-isomorphism instance easy.

Three practical examples

A graph-analysis tool can identify structurally duplicate small network patterns despite different vertex identifiers.
A component-model comparison can require matching node roles as well as connections.
A teaching exercise can demonstrate why graph drawings, degree sequences, and full isomorphism are different levels of comparison.

Think of it this way

Think of checking whether two wiring diagrams describe the same arrangement after replacing component names consistently. Every connection must line up under one shared renaming. The analogy is limited because real components may have attributes or directional behavior that are absent from a simplified graph, and those omitted properties cannot be verified by structural matching.

Worked example

Consider an original pair of simple undirected graphs. Graph G has vertices A, B, C, and D, with edges AB, BC, and CD. Graph H has vertices 1, 2, 3, and 4, with edges 1-3, 3-2, and 2-4.
A valid mapping is A→1, B→3, C→2, and D→4. Under this correspondence, AB becomes 1-3, BC becomes 3-2, and CD becomes 2-4. Both graphs have exactly those three path edges, so adjacency and nonadjacency agree under the mapping.
The vertex degrees also align: A and D have degree one, matching 1 and 4, while B and C have degree two, matching 3 and 2. These degree facts help constrain candidates, but the complete edge check establishes this particular isomorphism.
Now label A and D red and B and C blue. Give H the corresponding labels: 1 and 4 red, 2 and 3 blue. The mapping preserves both connections and labels, so it also establishes label-aware isomorphism.
Next swap the labels of vertices 1 and 3 in H. Both graphs still contain two red and two blue vertices, so matching total label counts alone does not detect the problem. However, G has two red endpoints, while H now has one blue endpoint and one red endpoint. Any structural isomorphism must map endpoints to endpoints because it preserves degree. No label-preserving mapping can therefore exist.
An unlabeled isomorphism check would still return a positive result because the edges did not change. A check configured to compare the color attribute should reject the relabeled pair. The distinction is an intended consequence of different comparison settings, not contradictory algorithm behavior.
For another limitation of preliminary checks, compare a six-vertex cycle with two disconnected triangles. Both have six vertices, six edges, and degree two at every vertex. They are not isomorphic because one is connected and the other is not. Equal degree sequences are useful screening information, not a complete proof.

Illustrative case study

In a fictional graph-catalog project, a team wants to remove duplicate workflow patterns. An initial structural comparison merges two patterns whose vertices have different operational roles.
The team defines which role attribute must be preserved and repeats the comparison with that requirement. It retains the returned correspondence for human inspection and documents how missing labels are handled. This fictional case illustrates the importance of graph semantics; it does not claim measured speed improvements or a deployed deduplication result.

Common misconceptions and mistakes

VF2++ does not compare graphs by their visual layout, and ordinary vertex names need not match. It also does not infer which business attributes are important.
Do not assume that matching counts or degrees proves isomorphism. Do not confuse full-graph isomorphism with finding a pattern inside a larger graph, which requires the appropriate subgraph problem and interface. Finally, the existence of one mapping does not mean it is unique. Symmetric graphs can admit several equally valid correspondences.

Business use

The method can support exact structural comparison in graph-based data workflows. Its usefulness depends on translating the real question into the right graph and matching conditions.
Before accepting a result, define whether direction, parallel edges, node labels, or other attributes matter. Inspect a returned mapping for representative cases and test deliberately mismatched examples. Record interface settings alongside results. A positive structural match should not be described as complete business equivalence when relevant information was excluded from the comparison.

Check your understanding

Why does swapping one endpoint label with an internal label invalidate label-aware matching while preserving structural matching?

Answer: The edge structure is unchanged, but no degree-preserving endpoint correspondence can now preserve all colors.

Related terms

Graph isomorphism
Subgraph isomorphism
Vertex mapping
VF2
Node label
Degree sequence
Graph automorphism
Search pruning

Learn next

Next, reverse the valid path correspondence: map A to 4, B to 2, C to 3, and D to 1 in the original correctly labeled H. Check every edge and label. Explain why finding this second mapping does not make either mapping incorrect.

Sources

Primary sources: NetworkX isomorphism overview: https://networkx.org/documentation/stable/reference/algorithms/isomorphism.html ; VF2++ Boolean API: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.isomorphism.vf2pp.vf2pp_is_isomorphic.html . The path mappings and counterexamples are original.

Previous: Very long instruction word Next: Vibe coding