This C++ program enumerates certain 3-regular 3-edge-colored graphs G on 2n vertices. Let the colors of the graph edges be called 1, 2, and 3. A face is a bicolored cycle whose edges alternate between two fixed and distinct colors. Now, consider that the original 3-colored graph G is combined with a perfect matching (pairing) M of its vertices. Assign to M a new color 0 and think of the combination of G and M as a new (3+1)-edge-colored graph. We are particularly interested in the total number of faces with colors (0,1), (0,2) and (0,3). Denote this number by F(M,G).

The program computes the maximum of F(M,G) over all perfect matchings M on 2n vertices, and identifies those graphs G where this maximum is ≤ 3n/2. For n ≤ 9, this happens only for n=8. It also counts the number of 3-edge-colored maximally single-trace graphs, i.e., edge-colored graphs with a single face for each pair of colors.

This is relevant to the research on random tensors. In this context, the 3-edge-colored graphs encode tensor model observables (trace invariants). The face counting is relevant for determining the expectation value of these observables, and crucially their scaling with the size N of the tensors.

The program only scans 3-edge colored-graphs that have a single face for one pair of colors—say colors (1,2): The vertices are labeled 0,1, ..., 2n-1. Color 1 is fixed to: {0,1} {2,3} ... {2n-2,2n-1}; color 2 is fixed to: {1,2} {3,4} ... {2n-1,0}; and only color 3 is varied. It uses the nauty library (McKay, B.D. and Piperno, A., "Practical Graph Isomorphism, II", Journal of Symbolic Computation, 60 (2014), pp. 94-112. doi:10.1016/j.jsc.2013.09.003. https://pallini.di.uniroma1.it) to identify isomorphic graphs. This significantly reduces redundant work for larger n.

For more details, see the related publication. For usage instructions, see the readme file.