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 \).

  • Variant

    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.

  • Variant

    Determine the number of cycles in \(G\) of length \(g\).

  • Variant

    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\).

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email