# How to test graph isomorphism with edge labels using IGraph?

**URL:** <https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104>\
**Category:** Usage\
**Tags:** Mathematica\
**Created:** [27 April 2025 20:15 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104 "2025-04-27T20:15:19Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![anhnha](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/anhnha/32/1169_2.png) [@anhnha](https://igraph.discourse.group/u/anhnha)\
**Post date:** [27 April 2025 20:15 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/1 "2025-04-27T20:15:19Z")

</div>

Is it possible to check for isomorphism of undirected graphs with edge labels (no vertex label) in IGraph?  
I have read the documentation on isomorphism in the package but haven’t figured out how to do it.  
Here is an example with three graphs:

```auto
g1 = EdgeTaggedGraph[{UndirectedEdge[0, 1, a], 
    UndirectedEdge[0, 1, b], UndirectedEdge[0, 2, c], 
    UndirectedEdge[0, 2, e], UndirectedEdge[0, 3, d]}, 
   EdgeLabels -> "EdgeTag"];
g2 = EdgeTaggedGraph[{UndirectedEdge[0, 1, c], 
    UndirectedEdge[0, 1, e], UndirectedEdge[0, 2, a], 
    UndirectedEdge[0, 2, b], UndirectedEdge[0, 3, d]}, 
    EdgeLabels -> "EdgeTag"];

g3 = EdgeTaggedGraph[{UndirectedEdge[0, 1, d], 
    UndirectedEdge[0, 1, e], UndirectedEdge[0, 2, a], 
    UndirectedEdge[0, 2, b], UndirectedEdge[0, 3, c]}, 
    EdgeLabels -> "EdgeTag"];
{g1, g2, g3}

```

 ![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/2X/f/fd511b2bdc231e5d8bcb3a95f89a3ca0197de567.png)

**g1** and **g2** are isomorphic when considering edge labels.  
**g1** and **g3** , or **g2** and **g3** , are not isomorphic when considering edge labels.

`IGIsomorphicQ` returns `True` for all of them, as it does not take edge labels into account.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [28 April 2025 08:01 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/2 "2025-04-28T08:01:06Z")

</div>

IGraph/M’s isomorphism functions never take the `EdgeLabel` property (which is solely for _display_ purposes) into account, but they do provide a way to supply “colours” for isomorphism algorithms. You will find examples in the documentation. Edge colours are only supported by the VF2 algorithm.

Provide edge colours in the order of the edge list:

```mma
In[266]:= IGVF2FindIsomorphisms[
 {CycleGraph[3], "EdgeColors" -> {1, 1, 2}},
 {CycleGraph[3], "EdgeColors" -> {1, 2, 1}}
 ]

Out[266]= {<|1 -> 2, 2 -> 1, 3 -> 3|>, <|1 -> 2, 2 -> 3, 3 -> 1|>}

```

Provide edge colours as associations. Some edges have no assigned colours:

```auto
In[268]:= IGVF2FindIsomorphisms[
 {CycleGraph[3], "EdgeColors" -> <|1 \[UndirectedEdge] 2 -> 1|>},
 {CycleGraph[3], "EdgeColors" -> <|2 \[UndirectedEdge] 3 -> 1|>}
 ]

Out[268]= {<|1 -> 2, 2 -> 3, 3 -> 1|>, <|1 -> 3, 2 -> 2, 3 -> 1|>}

```

Unfortunately, the graphs you show have multi-edges and our VF2 implementation does not support these. A workaround you can use is to somehow encode each set of parallel edges, with their associated colours, to a single edge with a new colour. I don’t have time to code this up this morning, but I hope the answer is useful.

---

<div class="post-metadata">

**Author:** ![anhnha](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/anhnha/32/1169_2.png) [@anhnha](https://igraph.discourse.group/u/anhnha)\
**Post date:** [28 April 2025 09:29 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/3 "2025-04-28T09:29:04Z")

</div>

Thanks for the information. Could you explain how to encode parallel edges? Simply treating all parallel edges as a single edge with the sum of their colors doesn’t always work.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [28 April 2025 09:52 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/4 "2025-04-28T09:52:57Z")

</div>

No, you would need to produce a new _unique_ colour ID for each colour combination that is found in the original two graphs. I would simply check what colour combinations are present, list them, and and assign a unique integer to each.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [28 April 2025 10:02 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/5 "2025-04-28T10:02:14Z")

</div>

Here’s a sloppy example that assumes that:

- There are no isolated vertices (since we build graphs from edges only)
- The “edge colour” is the edge tag

```auto
simplifiedGraphs = Table[
  GroupBy[EdgeList[g], Sort@Drop[#, -1] & -> Last],
  {g, {g1, g2, g3}}
  ]

colorCombinations = Union@Catenate@simplifiedGraphs

asc = AssociationThread[colorCombinations, 
  Range@Length[colorCombinations]]

Graph[#, EdgeLabels -> "EdgeTag"] & /@ 
 KeyValueMap[Append[#1, asc[#2]] &] /@ simplifiedGraphs

```

---

<div class="post-metadata">

**Author:** ![anhnha](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/anhnha/32/1169_2.png) [@anhnha](https://igraph.discourse.group/u/anhnha)\
**Post date:** [28 April 2025 10:30 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/6 "2025-04-28T10:30:04Z")

</div>

Thank you for the idea. I was considering the subdivision approach to convert it into a simple graph, but your method seems cleaner.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/szhorvat/32/3_2.png) [@szhorvat](https://igraph.discourse.group/u/szhorvat)\
**Post date:** [29 April 2025 18:31 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/8 "2025-04-29T18:31:15Z")

</div>

I’m sorry, I reverted the deletion of your last question because I do think it is related and relevant.

The answer is basically the same:

You can use the `IGVF2...Subisomorphisms` functions instead of the `IGVF2...Isomorphisms` to find a subgraph as part of a larger graph.

Currently, of the algorithms implemented in igraph, only VF2 supports edge colours, and it only handles simple graphs. So an encoding of multi edges similar to what I suggested above would be necessary.

Be aware that if you are requesting an exhaustive listing, all mappings will be returned. For example,

 ![image](https://global.discourse-cdn.com/free1/uploads/igraph/original/2X/7/73de371a9a3a53c14637d47d545f86c3b91e4621.png)

contains the triangle subgraph in 12 times, not just twice, according to these functions. This is because the a triangle maps to itself in 6 ways.

The same limitations apply as with the VF2 isomorphism functions.

---

<div class="post-metadata">

**Author:** ![anhnha](https://yyz2.discourse-cdn.com/free1/user_avatar/igraph.discourse.group/anhnha/32/1169_2.png) [@anhnha](https://igraph.discourse.group/u/anhnha)\
**Post date:** [1 May 2025 05:19 UTC](https://igraph.discourse.group/t/how-to-test-graph-isomorphism-with-edge-labels-using-igraph/2104/9 "2025-05-01T05:19:47Z")

</div>

Thanks again for the extra info!  
I realized after posting that the answer was already in the docs, so I deleted it.