Question: The strange behavior of IsSubgraphIsomorphic requires additional options to be easily checked

The IsSubgraphIsomorphic command accepts either two undirected graphs or two directed graphs as input.  It returns true if G1 is isomorphic to some subgraph of G2. The GraphTheory [IsSubgraphIsomorphic] command was introduced in Maple 2021.

If a graph T is isomorphic to some subgraph T' of  a graph GIsSubgraphIsomorphic(T,G)  will  return true. But there is no option to return T'. That makes it hard to check manually.

I've seen  IsSubgraphIsomorphic behaving strangely lately. I want to check whether K8-P6 contains K7-K3 as its subgraph.

T:=DeleteEdge(CompleteGraph(7),{{1,2},{2,3},{3,1}},inplace= false): 
G:=DeleteEdge(CompleteGraph(8),{{1,2},{2,3},{3,4},{4,5},{5,6}},inplace= false): 
IsSubgraphIsomorphic(T,G)

true

I think theoretically, the result of IsSubgraphIsomorphic is not correct. I also tested it from Mathematica, and it worked as I expected.

h = EdgeDelete[ CompleteGraph[7], {1 <-> 2, 2 <-> 3, 3 <-> 1}]; 
g = EdgeDelete[ CompleteGraph[8], {1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 6}]; 
IsomorphicSubgraphQ[h, g]

False

I wonder what went wrong.

 

PS: Subgraph isomorphism is a question I've asked before, and we can refer to the following links and code. https://www.mapleprimes.com/questions/226937-How-To--Test--A--Graph--Whether-Contains

with(GraphTheory):
with(combinat):
T:=DeleteEdge(CompleteGraph(7),{{1,2},{2,3},{3,1}},inplace= false): 
G:=DeleteEdge(CompleteGraph(8),{{1,2},{2,3},{3,4},{4,5},{5,6}},inplace=false): 
nE,nV := NumberOfEdges(T), NumberOfVertices(T):
# Produce all subgraphs of G which have the same number of edges and vertices as the "test" sub-graph T
U:=choose(Edges(G),nE): nops(%):
U1:=select(t -> (nops(`union`(t[]))=nV), U): nops(%):
gL:= Graph~(U1): nops(%):
ans:= [ seq
          ( `if`
            ( IsIsomorphic( T, gL[j] ),
              j,
              NULL
            ),
            j=1..numelems(gL)
          )
        ]:
if   numelems(ans)>0
then HighlightSubgraph( G, gL[ans[1]], edgestylesheet=[thickness=4, color="Red"]);
     DrawGraph(G, style=spring);
fi;

These codes are due to tomleslie  and  vv. According to above codes, it seems that there is something wrong with IsSubgraphIsomorphic too.

Please Wait...