The inverse problem of a mathematical question is often very interesting.

I'm glad to see that Maple 2023 has added several new graph operations. The GraphTheory[ConormalProduct], GraphTheory[LexicographicProduct], GraphTheory[ModularProduct] and GraphTheory[StrongProduct] commands were introduced in Maple 2023.

In fact, we often encounter their inverse problems in graph theory as well. Fortunately, most of them can find corresponding algorithms, but the implementation of these algorithms is almost nonexistent.

I once asked a question involving the inverse operation of the lexicographic product.

• https://www.mapleprimes.com/questions/235863-An-Inverse-Problem-Of-Lexicographic

Today, I will introduce the inverse operation of line graph operations. (In fact, I am trying to approach these problems with a unified perspective.)

To obtain the line graph of a graph is easy, but what about the reverse? That is to say, to test whether the graph is a line graph. Moreover, if a graph  g is the line graph of some other graph h, can we find h? (Maybe not unique. **Whitney isomorphism theorem tells us that if the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph K_3 and the claw K_{1,3}, which have isomorphic line graphs but are not themselves isomorphic.)

Wikipedia tells us that there are two approaches, one of which is to check if the graph contains any of the nine forbidden induced subgraphs. 

Beineke's forbidden-subgraph characterization:  A graph is a line graph if and only if it does not contain one of these nine graphs as an induced subgraph.

This approach can always be implemented, but it may not be very fast. Another approach is to use the linear time algorithms mentioned in the following article. 

• Roussopoulos, N. D. (1973), "A max {m,n} algorithm for determining the graph H from its line graph G", Information Processing Letters, 2 (4): 108–112, doi:10.1016/0020-0190(73)90029-X, MR 0424435

Or: 

•   Lehot, Philippe G. H. (1974), "An optimal algorithm to detect a line graph and output its root graph", Journal of the ACM, 21 (4): 569–575, doi:10.1145/321850.321853, MR 0347690, S2CID 15036484.

SageMath can do that: 

   root_graph()

Return the root graph corresponding to the given graph.

    is_line_graph()

Check whether a graph is a line graph.

For example, K_{2,2,2,2} is not the line graph of any graph.

K2222 = graphs.CompleteMultipartiteGraph([2, 2, 2, 2])
C=K2222.is_line_graph(certificate=True)[1]
C.show() # Containing the ninth forbidden induced subgraph.

Another Sage example for showing that the complement of the Petersen graph is the line graph of K_5.

P = graphs.PetersenGraph()
C = P.complement()
sage.graphs.line_graph.root_graph(C, verbose=False)

(Graph on 5 vertices, {0: (0, 1), 1: (2, 3), 2: (0, 4), 3: (1, 3), 4: (2, 4), 5: (3, 4), 6: (1, 4), 7: (1, 2), 8: (0, 2), 9: (0, 3)})

Following this line of thought, can Maple gradually implement the inverse operations of some standard graph operations? 

Here are some examples:

•   CartesianProduct
•   TensorProduct
•   ConormalProduct
•   LexicographicProduct
•   ModularProduct
•   StrongProduct
•   LineGraph
•  GraphPower

Recently, ChatGpt has gained a lot of attention and there are mixed reviews about it. Some people think highly of its capabilities, while others are more critical. Regardless, it has been an interesting  topic on assistant programming.

I'm going to give two examples to illustrate what's interesting and what's lacking.

First, I want ChatGpt to write a Maple code for the enumeration of all prime numbers up to 100. Then it writes:

primes:= proc(n)
   local i, j, primes;
   primes:= [2];
   for i from 3 to n do
      for j from 2 to i-1 do
         if i mod j = 0 then break;
      end do;
      if j = i then primes:= [op(primes), i]; end if;
   end do;
   return primes;
end proc;

primes(100);

I copy and paste this code, maple shows an error: Error, reserved word `do` unexpected

I report the error to it:

this code cannot run since "Error, reserved word `do` unexpected"

Then it gives: I apologize for the error in the previous code. Here is a corrected version of the code that can be run in Maple:

primes:= proc(n)
   local i, j, primesList;
   primesList:= [2];
   for i from 3 to n do
      for j from 2 to i-1 do
         if i mod j = 0 then 
            break;
         end if;
      end do;
      if j = i then 
         primesList:= [op(primesList), i]; 
      end if;
   end do;
   return primesList;
end proc;

primes(100);

Ok, It's tediously written code, but at least it's correct. 

Furthermore, I ask:

Is there a more concise approach that utilizes maple's built-in functions.

It tells me:

Yes, there is a more concise approach that utilizes Maple's built-in functions. Here's an example:

primes := [seq(i, i=2..100)]; primes := [op(select(isprime, primes))];

The seq function generates a list of numbers from 2 to 100. The select function filters out all non-prime numbers using the isprime function, which tests the primality of a number. The result is stored in the primes array.

Ok, this answer meets my expectations.

Another example is the generation of all 6th order non-isomorphic graphs, which pops up as:

# Load the GraphTheory package
with(GraphTheory):

# Generate a list of all non-isomorphic graphs with 6 vertices
graphs := NonIsomorphicGraphs(6):

# Print the list of non-isomorphic graphs
print(graphs);

But NonIsomorphicGraphs(6) as we know is the number  of non-isomorphic graphs but  not graphs  themselves.

So I say:

in the above codes, NonIsomorphicGraphs need the options output = graphs, outputform = graph

ChatGpt gives :

Here is a revised version of the code that takes into account the options output = graphs and outputform = graph:

# Load the GraphTheory package
with(GraphTheory):

# Generate a list of all non-isomorphic graphs with 6 vertices
graphsList := NonIsomorphicGraphs(6, output = graphs, outputform = graph):

# Print the number of non-isomorphic graphs
print("Number of non-isomorphic graphs: ", nops(graphsList));

# Print each non-isomorphic graph in the list
for i in 1 to nops(graphsList) do
  print("Graph ", i, ": ", graphsList[i]);
end do

It still has syntax errors. I made some artificial adjustments.

# Load the GraphTheory package
with(GraphTheory):

# Generate a list of all non-isomorphic graphs with 6 vertices
graphsList := [NonIsomorphicGraphs(6, output = graphs, outputform = graph)]:

# Print the number of non-isomorphic graphs
print("Number of non-isomorphic graphs: ", nops(graphsList));

# Print each non-isomorphic graph in the list
for i from 1 to nops(graphsList) do
  print("Graph ", i, ": ", graphsList[i]);
end do;

I pulled a wry face when  it builds a lot of codes  that do not exist in Maple.. Here's a little tidbit of my conversation with it.

This software still needs more work. I'm not sure how far it can go, but maybe programming becomes easier. Maybe more interesting examples will be found.