Exists m n k ------------ This software is covered by the CRAPL licence (see CRAPL-LICENSE.txt) What Exists? ------------ Does there exist a simple graph with m vertices (i.e. order m) and n edges (i.e. size n) that contains no cycles of length k-1 or less (i.e. has girth k)? Required Software ----------------- The program uses choco-2.1.0-basic.jar and a copy of it is in this directory or available from the choco web site http://www.emn.fr/z-info/choco-solver/ You will need to get the CLASSPATH to point to this (no help given here). Compiling --------- Do the following on the command line >javac *.java Running ------- The program Exists takes as arguments - m, the number of vertices in the graph (order) - n, the number of edges in the graph (size) - k, the minimum girth of the graph - [witness] optional argument It is run as follows (for example) > java Exists 10 25 4 true 25[+0] millis. 34[+0] nodes This says "Yes! There is a graph with 10 vertices and 25 edges of girth 4 and it took me 25 milliseconds to discover this and I had to make 34 decisions." You might run it as follows >java Exists 10 25 4 witness 0 0000011111 1 0000011111 2 0000011111 3 0000011111 4 0000011111 5 1111100000 6 1111100000 7 1111100000 8 1111100000 9 1111100000 24[+0] millis. 34[+0] nodes This then delivers a witness as a 0/1 adjacency matrix for a graph with those properties. But what happens when there is no such graph? >java Exists 10 26 4 false 249[+0] millis. 446[+0] nodes It delivers false (and if you ask for a witness "no witness"). If we have already run with n=10, m=25 and k=4 and got "yes!" then we know that this is "extremal". NOTE: ----- This program is not optimized in any way whatsoever. It does not take into consideration any features of the problem. It is slow. See the CRAPL license. Patrick Prosser 19/04/2013