Reduction of symmetric configurations \(n_3\) (Q1962060)

A configuration \((v,b)\) is an incidence structure with the following properties: (a) There are \(v\) points and \(b\) lines. (b) There are \(k\) points on each line and \(r\) lines through each point. (c) Two different lines intersect at most once and two different points are connected by at most one line. If \(v=b\) (and hence \(r=k\)) then the configuration is called symmetric and denoted by \(v_k\). Configurations were defined by Reye. It was in 1887 V. Martinetti gave a construction method for the symmetric configurations \(n_3\). Given a configuration \(n_3\), if possible remove two parallel (non-intersecting) lines \(a\) and \(b\) and two points \(A_0\) and \(B_0\) from \(a\) and \(b\) respectively which are not on a common line. Add a new point \(Z\) and three new lines \(\{Z,A_1,A_2\}\), \(\{Z,B_1,B_2\}\), \(\{Z, A_0, B_0\}\) through \(Z\). A configuration \((n+1)_3\) is obtained. This procedure is called reducible, which is not always possible. Also this method does not cover the irreducible configurations. Some famous configurations \(n_3\) are the Fano plane \(7_3\), the Pappus configuration \(9_3\) and the Desargues configuration \(10_3\) which are all important in projective and affine geometry. Interestingly there is an interpretation of a configuration of \(n_3\) as a graph \(G(n_3)\). We could think of the lines as white vertices and the points as black ones. Two vertices are connected by an edge, if the corresponding line and the point are incident. Since to lines intersect at most once and two points are connected by at most one line, the graph contains no cycle of length 4. The girth is greater than or equal to 6. The symmetric configurations \(n_k\) are \(k\)-regular bipartite graphs. The configurations \(n_3\) we are interested in are 3-regular bipartite graphs, the so-called bicubic graphs, with girth at least 6. An example of this interpretation for the Fano plane \(7_3\) which is a Heawood graph \(F\) is given in this paper. In fact Martinetti's result leaving infinitely many irreducible configurations motivate the development of a generalized reduction procedure by means of which every \(n_3\) can be reduced to \(F\). The authors prove that there exists a finite number of generalized Martinetti-like reduction procedures, such that every bicubic connected graph \(G\) with girth at least 6 different from the Fano-Heawood graph \(F\) can be reduced to a smaller one of the same kind, having two vertices less, and by iteration to \(F\).