Find all minimal edge cuts of a connected undirected graph using fundamental cutsets. (Assume no self-loops or multiple edges.)
The MinimalEdgeCuts procedure is in the startup code edit region (See Edit -> Startup Code.) (and is reproduced at the end of the worksheet).

Choose a graph.

The objective is to find all minimal edge cuts. If we partition the vertices of a graph in two non-empty sets (parts), then a cut is defined as a set of edges of the graph that have one end in the first part and the other end in the second part. Removal of these edges breaks the graph into two (or more) disconnected components.

For example the cut with edges {1,2} and {2,3} leaves two components with vertices [1,3,4] in one component and vertex [2] in the other component.

A cut is minimal if adding back any of the edges makes it connected again, i.e, the cut leave only two components. The above cut is minimal. Sometimes the term cutset is used to mean a minimal cut, but sometimes, as in Maple's IsCutSet, cutset means any removal of edges that increases the number of components.

This graph has 6 minimal cuts:

This partitioning process suggests a brute force algorithm to find all minimal cuts. Find all partitions of the vertices into two (non-empty) sets. The two induced subgraphs  and  have some of the edges of the graph. All edges of the graph that are not in the two subgraphs form a cut. For example for the above partition we have:

Now we have to check that each component is connected, or that there are a total of two components. Since there are in this case, the cut is minimal.

Note that we do have to test that there are only two components. For example for the path graph 1--2--3, the partition [[2],[1,3]] has three components (the three individual vertices). The associated cut {{1,2},{2,3}} is not minimal because we could put edge {1,2} back and the graph would still be disconnected.

The number of partitions to be tested is , where n is the number of vertices. Any subset of the vertices could be in the first set (except the empty set and the set of all vertices), and then the other vertices must be in the second set. However that will give double the possibilities, since swapping set 1 and set 2 makes no difference. In the present case there are  possibilities, as seen below, where 0 indicates that the vertex in that position is in set 1 and 1 indicates that it is in set 2. For example, possibility 4 is the above partition .

   1 2 3 4
1: 0 0 0 1
2: 0 0 1 0
3: 0 0 1 1
4: 0 1 0 0
5: 0 1 0 1
6: 0 1 1 0
7: 0 1 1 1

The algorithm described is implemented as procedure MinimalEdgeCutsPartition in the startup code. (The minimal cuts are not produced in the same order as above.)

However, a better approach is by building up the cuts fron a set of fundamental cuts (or cutsets, using the word in the restrictive sense). These are associated with a spanning tree. We choose any spanning tree, which we highlight with red edges. This is a tree graph (connected with no cycles) that has the same vertices as the graph.

Any spanning tree graph has  edges. This is also the number of vertices minus the number of connected components (=1), which is the rank of the graph, which we will call .
We will find one fundamental cutset for each edge of the tree, so there will be  fundamental cutsets.

Select one of the tree edges, say {1,2}. Removal of this edge partitions the tree into two components. We find the vertex partition and the corresponding cut by the procedure above. (We do not have to test for only two components because that follows from the tree structure.). This is the example we did above. The first three cuts in mincuts are the fundamental ones. Each one has one of the tree edges.

It is possible to generate all the cuts of the graph involving the tree edges by taking all  subsets of the set of fundamental cutsets (this includes the empty set), and adding the elements of each subset with a ring sum operation.

A ring sum of two edge sets includes all edges in both sets except those that are common to both (the symmetric difference or disjunctive union):

(Maple has this as the symmdiff command, but not in infix form.)
We can also represent a set of edges by a vector, with entry 1 if the corresponding edge is in the set and 0 otherwise. The edge order we choose here is the order in . Then the ring sum operation is the same as addition modulo 2 of the corresponding vectors, though we won't make much use of this in implementing the algorithm. Set up to convert to vectors.

Let's try the ring sum on f[1] and f[2]. It is a cut, and since it now has two tree edges it is not a fundamental cut. (It happens to be minimal because it splits the graph into two components.)

Do the same thing in the vector representation. The same logic about the tree edges (first three entries) shows the fundamental vectors are basis vectors and the three vectors are linearly independent (with respect to the addition mod 2 operation).

The ring sum of any two cuts is another cut, which may be minimal (a cutset) or a disjoint union of cutsets (= two cutsets together). Combining the elements of the 8 subsets gives the eight cuts for this graph associated with the chosen tree graph, i.e., it has all combinations of tree edges. In vector form they are:

Although we constructed these cuts relative to a specific spanning tree, they can be shown to be all the cuts of the graph. Consider the set of all edges of the graph. It might seem that this is a cut that has been missed, because it separates the graph into two or more (actually 4) components. However, looking at the edges

and recalling the definition of a cut, we see that this is not actually a cut. We need the edges in a cut all to have one end in one set of vertices and the other end in the set of other vertices, and this is not possible here. (Maple's IsCutSet is not this strict and returns true.) We can show it is not possible with IsBipartite.

Although we have found all cuts, we now need to test them to find which ones are minimal. The first case with no edges does not cut the graph into two components and we reject it. (It is usually included as a cut to make the cuts into a vector space.)  The 6th one is not minimal. Its first and third entries are 1, meaning it is the ring sum of the first and third fundamental cuts. It splits the graph into three components:

This is a case where the ring sum is a disjoint union (not minimal), and arises because f[1] and f[3] have no edges in common:

For the present graph, all but the empty set and  are minimal, and so there are 6 minimal cuts. In vector form:

So the algorithm is to generate all cuts and test them for minimality. If we neglect the empty cut, then we have to generate  cuts for testing. This is the same as the number of partitions that we generated in the partition algorithm. However, for the fundamental cuts we do not need to test that the components are connected, and more importantly, the ring sum is a more efficient way of finding the edges than partitioning and then using InducedSubgraphs.

The tests for minimality can be made more efficient by finding cases that can be classified without having to check the number of components. Two simple cases with modest savings (implemented here) are:

1. The fundamental cuts are minimal by construction.

2. If two cuts have no edges in common, then the ring sum is a disjoint union and is not minimal. This is the case for example for f[1] and f[3].

There may be other ways to classify without doing the more difficult minimality test, for example variations of (2.) for ring sums with more than two cuts. Hovever, the cutset algorithm is already significantly more efficient than the partition algorithm. Perhaps working with the vectors would be more efficient. Other more efficient algorithms may be known that I am not aware of.

The MinEdgeCuts algorithm in the startup code is reproduced here:

Recently @Nour asked (in part) if Maple can simplify 2*(x^2 - x*y - x*z + y^2) to (x - y)^2 + (y - z)^2 + (z - x)^2. User @vv pointed out that a sum of squares form is not unique. I'm not sure if @Nour's intent was to show that this was always non-negative, but even if the sum of squares form is not unique, it does help to demonstrate that the expression will be nonnegative for all real x,y,z. This reminded me that I have over the years had cases where I wanted to know if a quadratic form (multivariate polynomial with all terms of degree 2) would always be non-negative (a quadratic form will be zero if all variables are zero, so we know it won't always be positive). I have typically done this by hand in the following way, which I demonstrate for the simpler case

We make a (column) vector of the variables, v = [x,y] and then construct the symmetric Matrix A for which Transpose(v).A.v is the required expression. For the squared term 2*x^2, the coefficient 2 is put in the diagonal entry A[1,1] and likewise 4*y^2 leads to A[2,2] = 4. The term -3*x*y comes from the sum A[1,2]+A[2,1] and so half of the coefficient -3 goes to each of A[2,1] and A[1,2]. The Matrix is therefore

The Matrix is found to be positive definite (positive eigenvalues), which means that the quadratic form is positive for all non-zero real vectors v.

One way to get the sum of squares form is to use the Cholesky decomposition (for positive definite or semidefinite matrices), which yields A = L.Transpose(L) = L.I.Transpose(L), and then note that Transpose(L).v is a change of variables to a diagonal quadratic form

so we have

and we have rewritten the quadratic form in an explicitly nonnegative form.

Another way to the sum of squares would be via the othogonal similarity A = U.Lambda.Transpose(U), where U is an orthogonal matrix of eigenvectors and Lambda is diagonal with eigenvalues on the diagonal. This form works even if the matrix is not positive (semi)definite.

In this simple case, Maple has some other ways of showing that the quadratic form is non-negative for real x,y

Without assumptions, is correctly decides p1 is not always nonnegative, and an example of this for complex x and y is easily found. With assumptions, is fails.

At least in Maple 2017, solve suggests any x and y will do, which is not quite right

In the next worksheet, I implement this method in a general procedure IsQformNonNeg, which works as well as IsDefinite does. For most cases of interest (integer or rational coefficients) there are no problems. For floating point coefficients, as always, numerical roundoff issues arise, and I dealt with this by giving warnings. (Rank is more robust in these cases than IsDefinite, but since this case can be better dealt with by converting floats to rationals, I haven't worked too hard on this - perhaps IsDefinite will be improved.)

The original example 2*(x^2 - x*y - x*z + y^2)  is dealt with as an example in the next worksheet