Graphs of projective planes
Task number: 3900
Let \( (X, \mathcal P) \) be a finite projective plane of order \( q \). Let’s construct a bipartite graph \( G = G (X, \mathcal P)\) with the classes of bi-partition \( X \) and \( \mathcal P \) so that a point \(x\in X\) and a line \(p \in\mathcal P \) are joined by an edge if and only if \( x \) belongs to \( p \).
Determine the girth \(g\) of the graph \( G \). The girth of a graph that contains at least one cycle is the smallest length of such cycle.
Determine the number of cycles in \(G\) of length \(g\).
Let \( H \) be a bipartite \((q+1)\)-regular graph (i.e. each vertex has degree \(q+1\)) for \(q\geq 2 \), without cycles of size \(4\) and such that between each two vertices there is a path of length at most 3.
Prove that \(H\) is isomorphic to \( G(X’,\mathcal P’) \) for some finite projective plane \((X’,\mathcal P’)\) of order \(q\).