In graph $G$, to determine whether two vertices have the same status, we can look for orbits for these two vertices in the automorphism group of graph $G$.

By Mathematica, the automorphism group of the above graph is as follows:

PermutationGroup[{Cycles[{{6, 7}}], Cycles[{{4, 5}}], 
  Cycles[{{1, 2}}], Cycles[{{1, 4}, {2, 5}}], Cycles[{{8, 9}}]}]

Its orbit is as follows:

{{1, 2, 4, 5}, {3}, {6, 7}, {8, 9}}

So $1$, $2$, $4$ and $5$ have the same status. "Same status" is my own understanding, it means the element is in the same orbit in its automorphism group.

We are trying to broaden this problem a bit.

How can we use the automorphism group (or other things) of a graph to describe that two subgraphs have the same status in the graph?

But here "same status" of the two subgraphs is based on my intuition. I am not sure how to define it rigorously yet. For example, in the following graph, triangles $T^1$ and $T^2$ have the same status (symmetric); triangles $T^4$ and $T^5$ have the same status (symmetric).

Note that $T_1:=[1231], T_2=[3453], T_3=[3673],T_4=[6786],T_5=[6796]$.

Triangle $T^1$ is not symmetric with any of the three triangles $T^3$, $T^4$ and $T^5$.

enter image description here

Ps: In the end, I would like to write a program to determine whether two subgraphs have the same status.

  • $\begingroup$ When you say that two subgraphs of a graph $\Gamma$ have the same status do you mean that there is an automorphism of $\Gamma$ that maps one to the other? $\endgroup$
    – Derek Holt
    May 1 at 13:31
  • $\begingroup$ Yes, I feel that what you said meets my expectations, but I don't know how to determine whether such an automorphism exists or how to find such an automorphism. It seems that we need to find all the automorphisms and then check whether they map the two subgraphs. $\endgroup$
    – licheng
    May 1 at 13:37
  • $\begingroup$ You can do that using existing software, such as GAP (with the GRAPE package for graph automorphism) or Magma. Just compute the automorphism group of the graph and then test whether there is an automorphism mapping the vertex set of one subgraph to the other. $\endgroup$
    – Derek Holt
    May 1 at 14:46
  • 1
    $\begingroup$ Thank you for recommending nice softwares. Just from the automorphic map of a graph does not seem to reflect the symmetry of two subgraphs. For example, the subgraph $T^1$ and subgraph $\{\{4,5\},\{3,5\}\} $ . Obviously they cannot be said to be symmetric since the number of edges is different, but their vertices have an automorphism ((1,4)(2,5)). I hope I made it clear. Or I miss something. $\endgroup$
    – licheng
    May 1 at 16:02
  • $\begingroup$ Yes that's true. So you want to know if there is an element in the automorphism group that simultaneously maps a set of vertices to another set of vertices and also a set of edges to another set of edges. This is equivalent to testing whether the intersection of two cosets of different subgroups is non-empty. There is some discussion of this problem in GAP here. Of course if the group is not too big then you can just use a naive search. $\endgroup$
    – Derek Holt
    May 1 at 16:28

1 Answer 1


Let $T_1$ and $T_2$ be two subgraphs of $G$. Take two disjoint copies of your graph $G_1$ and $G_2$. Color the edges of $T_1$ in $G_1$, and the edges of $T_2$ in $G_2$.

Your subgraphs are equivalent if there exists an isomorphism between $G_1$ and $G_2$ that maps colored edges with colored edges, and non-colored edges with non colored edges.

Nearly all graph isomorphism solvers support colors on vertices. For colors on edges, if it is not supported, a solution is to subdivide each edge, color each old vertices with a specific color, and color the remaining vertices following our edge colors. Here, you just have to subdivide the edges of the subgraphs, and to color the new vertices with a new color. The documentation of Nauty suggest an approach by layers. It seems to create much more vertices, but might be more efficient in practice.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .