@dharr Great! (eps looks good.) I have another question. How do the black vertices cover the blue curve (the part that falls inside the black vertices)?

with(plottools):    
with(plots):
Bezier:=proc(x0,y0,x1,y1,x2,y2,x3,y3)
local f,g,c,l1,l2,l3,p0,p1,p2,p3;
f:=t->x0*(1-t)^3+3*x1*t*(1-t)^2+3*x2*t^2*(1-t)+x3*t^3:
g:=t->y0*(1-t)^3+3*y1*t*(1-t)^2+3*y2*t^2*(1-t)+y3*t^3:
c:=plot([f(t),g(t),t=0..1],thickness=2,scaling=constrained, color=blue,axes=none):
p0:=disk([x0,y0],0.02,color=black):
p1:=disk([x3,y3],0.02,color=black):
display(p0,p1,c,size=[300,300]);
end:
x0:=0:   y0:=0:
x1:=-0.2:  y1:=0.2:
x2:=0.5:  y2:=0.2:
x3:=0.3:  y3:=0:
Bezier(x0,y0,x1,y1,x2,y2,x3,y3)

@acer It's wonderful. My intention was to find out how the  SAT-solver works. As for the rest, I think I would be equally interested if you wrote the grame (an interative application, with in which clicking on any square caused the colors to flip, with the ability to reset with a random Matrix)

@justauser Yes, indeed. Thank you so much. 

@justauser I ran it not on the windows command line, but on the maple Command-line.

What you said is correct. I can use it successfully.

I just thought that since maple provides Maple-Commad-line, it would be easy to use it there as well.

@justauser That's great, but I still have one question. Why can't we enter "  E:\6conn.txt" directly on the Common-line? Isn't the Command-line equivalent to your codes "C:\Program Files\Maple 2022\bin.X86_64_WINDOWS\cmaple.exe". 

@Carl Love You say:

• Unfortunately, this command doesn't give the face-to-vertex correspondence;

Mathematica's DualPlanarGraph  provides a  dual graph with a face-to-vertex correspondence.

G = Graph[{1, 2, 3, 4, 5, 6, 7, 8}, {Null, SparseArray[Automatic, {8, 8}, 0, {1, {{0, 4, 8, 12, 16, 20, 24, 28, 32}, {{2}, {4}, {5}, {8}, 
    {1}, {3}, {5}, {6}, {2}, {4}, {6}, {7}, {1}, {3}, {7}, {8}, {1}, {2}, {6}, {8}, {2}, {3}, {5}, {7}, {3}, {4}, {6}, {8}, {1}, {4}, {5}, {7}}}, Pattern}]}, {FormatType -> 
    TraditionalForm, VertexCoordinates -> {{-0.707, 0.707}, {-0.707, -0.707}, {0.707, -0.707}, {0.707, 
    0.707}, {-0.354, 0.}, {0., -0.354}, {0.354, 0.}, {0., 0.354}}}, VertexLabels -> Automatic]

DualPlanarGraph[%, VertexLabels -> Automatic]

This may not be “difficult” to implement in maple. 

A planar graph and its dual graphs can also be embedded (simultaneously) on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. (simultaneously embedding problem)

• https://www2.cs.arizona.edu/~kobourov/dual_drawing.pdf

But I have not found for the code implementation right now.

@Carl Love I tried the following code for contract two independent edges. But it doesn't seem to be quite right. The weighting matrix of the graph obtained by contracting two independent edges seems strange, as if it's not symmetric. My understanding is that since the two contracted edges are independent, each edge of the new graph has a weight of at most 2. The appearance of "3" surprised me. (why)

Contractm:=proc(g,edge)
 local G, g1, v1,v2,v1adj,v2adj, comadj_v1v2,adofv2,gnew0,addedges,i;
    if IsWeighted(g)=false then
       G:= MakeWeighted(g):
    else 
       G:= g:
   end if:
         v1:=edge[1];
         v2:=edge[2];
         v1adj:= {op(Neighborhood(G, v1))}:
         v2adj:= {op(Neighborhood(G, v2))}:
         comadj_v1v2:=`intersect`(v1adj,v2adj): #The common neighborhood of v1 and v2
         adofv2:= `minus`(`minus`(v2adj,v1adj),{v1}): # The neighborhood of v2 minus the neighborhood of v1 and v1 itself.
         gnew0:= DeleteVertex(G,v2):
         addedges:={seq([{v1,i},1], i in adofv2)}:
         for i in addedges do
           AddEdge(gnew0, addedges);
         end do:
         for i in comadj_v1v2 do
           SetEdgeWeight(gnew0, {v1,i}, 2):
         end do: 
         gnew0:
end proc:

g:=ConvertGraph("O~tIID@wL~j`PbOqgLJ@p");
g1:=Contractm(g,{1,2}):
g2:=Contractm(g1,{4,5}):
plots:-display(DrawGraph~(<g| g2>));

WeightMatrix(g2); #GetEdgeWeight(g2, {4,11}) 
MaxFlow(g2,1,4);  # 6 may be aslo wrong.

Edits. Sorry.  I did not see Carl Love's latest reply. But I find it strange that the WeightMatrix of g2 from my codes is not symmetric. 

@Carl Love Here a single edge contraction may should retain multiple edges. Otherwise something will go wrong. 

Again, I use the example from the question.  First according to the  step 1 of the algorithm we choose an edge {1,2}. Clearly, {4,5} and {1,2} are independent in g. We then contract the edge {1,2} of g to the vertex "1" and immediately after,  we contract the edge "{4,5}" to the vertex  "4" . We note that the minimum separating set of "1" and "3" is 5 in the final graph.

with(GraphTheory):
g:=ConvertGraph("O~tIID@wL~j`PbOqgLJ@p");
g1:= Contract( Contract(g, {1,2}),{4,5});
plots:-display(GT:-DrawGraph~(<g| g1>));
g2:=MakeWeighted(g1):
MaxFlow(g2,1,4)

5

So M({1,2}, {3,4})= 5 if we delete these multiple edges. Thus the restricted-edge-connectivity of g is at most 5 since restricted-edge-connectivity =min{M(e_i-e_j)| unorder independent pairs e_i,e_j ∈ E}).) This contradicts the fact that the edge-connectivity of g is 6 (note that the restricted-edge-connectivity of g >= the edge-connectivity of g). 

So I'm guessing that a single edge contraction should retain multiple edges created in the process. However maple's graph theory package does not seem to support multiple edges. 

As shown below, we might should keep e₁ and e₂ when we contract the edge e. (?)

I don't know if I've misunderstood something.

@Carl Love Indeed contracting those two edges is the right choice. Thank you very much, that almost solves the problem.

@Carl Love First of all, thank you for your interest in this issue. The definition of the specific notation can be found in the following article. (also mentioned in the text).

• Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information processing letters, 1988, 27(4): 195-199.

For the sake of understanding, I will give a detailed explanation here.

• I(v) is the set of edges connected to v. (you are right)

Two edges in G are said to be independent if they do not have a common endvertex.

Let e_i and e_j be independent edges of G. An (e_i−e_j) edge separator is a set of edges S⊆E(G)−(e_i,e_j), such that the removal of S from G will destroy every path from any endvertex of e_i to any endvertex of e_j.

• Let M(e_i,e_j) represent the least cardinality of an (e_i−e_j) edge separator.

Clearly, computing M(e_i,e_j)  is the key to the whole algorithm.

According to the author, computing it should be polynomial. But I couldn't find it in anywhere. I even think it could be a separate question.

PS (can be skipped): I was going to use the function MaxFlow.  But it was found not to meet the requirements.  

• An edge separator of two vertices x and y is a set of edges S, such that the removal of S from G will destroy every path from  x to y.

Then MaxFlow(G,x,y) can compute the minimum edge separator of two vertices x and y. ( (According to the maximum-flow minimum-cut theorem, the maximum-flow function can be used.)

Let uv and xy be two edges of a graph. We can calculate the minimum edge separator  of  u and x,   u and y, v and x, and v and y, respectively.

But any value of MaxFlow(G,u,x)  , MaxFlow(G,u,y) ,MaxFlow(G,v,x) and MaxFlow(G,v,y) may not equal to M(uv,xy).  

There are two reasons for this：

1. The edge separation of u and x may use uv or xy (or use all the two edges uv and xy) , while  (e_i−e_j) edge separator is not using the edges uv and xy. (Similarly, v and x etc.) 
2. Even if the first item is solved, a minumum edge separator of  v to x (or of v to x, of v and y, or of u and y )  does not necessarily equal to M(uv,xy) (by definition of M(uv,xy)).   So taking their minimum value is not necessarily correct.

@Carl Love It would be nice if Mapleprimes could see the record of modifications, including deletions and flagged duplications, as Stack does.

@Carl Love I describe an equivalent question for this issue in the comments. But it is not clear to me yet:

• For a fixed k, what is the algorithm complexity for finding all k-cliques of a given graph?

In any case it is necessary to provide a relatively efficient function to find all k-cliques in maple.

Edits: Algorithm to find cliques of a given size k【O(n^k) time complexity】 

• https://iq.opengenus.org/algorithm-to-find-cliques-of-a-given-size-k/

But I cannot guarantee the authority of the information.

I think we can transform this set problem into a graph problem. 

We construct the corresponding graph as follows:

• set each subset Ei as a vertex, and
•  Ei is adjacent to Ej if and only if  Ei and Ej do not intersect.

This problem is then equivalent to finding all  cliques of size L of the graph. 

Unfortunately,  currently maple does not provide ready-made functions. As far as I know, IGraphM that is a Mathematica package for use in complex networks and graph theory research has this feature. I don't have too many ideas to implement IGCliques in maple yet.

S = {{{2, 3}, {2, 7}}, {{1, 3}, {2, 4}}, {{2, 4}, {2, 5}}, {{2, 
     6}, {1, 2}}};
G = RelationGraph[DisjointQ[#1, #2] &, List @@ S];
G1 = VertexReplace[G, Table[S[[i]] -> Subscript["S", i], {i, 4}]];
<< IGraphM`;
IGCliques[G1, {3}](*find all 3-cliques*)

{S1, S3, S4},  {S1, S2, S4}

It is found in [1] that there are 256 possible products of any two graphs using the adjacency and the non-adjacency relations of these graphs.  I think all these products can be handled with the function RelationGraph by Carl Love.  

sum(binomial(8, i),i=0..8)#Make a choice in each item, i.e., 2^8=256

[1] Barik, S., Bapat, R.B., Pati, S.: On the Laplacian spectra of product graphs. Appl. Anal. Discrete Math. 9, 39–58 (2015)

Out of these, four graph products namely, the Cartesian product (condition 1 or condition 7), the direct product (condition 3), the strong product (condition 1 or condition 3 or condition 7) and the lexicographic product (condition 1 or condition 3 or condition 5 or condition 7) are known as the standard graph products and have been studied by many researchers.

Here the conormal product is given by choosing the condition 1 or condition 3 or  condition 4 or  condition 5 or condition 7. It chooses “condition 4” more than the lexicographic product.

Therefore, the problems of computing products of two graphs in the future can be regarded as variants of the same problem on the mapleprimes, if not discussing the efficiency problem.

@vs140580 For your first problem:

You say in the post:

 I wonder if you missed a full-stop in that sentence. Is it supposed to be:

or:

I gave you an example, and please check if I understand correctly.

We can find at most three copies of G1 in G2 that are edges disjoint. Is "3" the answer you want?

I'm very interested in whether your C++ program can handle this example I'm talking about?