At least how many vertices does a graph have in which there is no cycle shorter than 6 and the degree of every vertex is 3?
Solution. We will show that the graph has at least 14 vertices, and there exists a 14-vertex graph that meets the conditions.

Let $A$ and $B$ be two vertices of the graph that are connected by an edge. Then from $A$ and $B$, two more edges each must emanate. The endpoints of these edges must be different, because if any two of them coincided, there would be a 3-length cycle in the graph. Let the other two neighbors of $A$ be $A_{1}$ and $A_{2}$, and the other two neighbors of $B$ be $B_{1}$ and $B_{2}$. Then $A_{1}, A_{2}, B_{1}$, and $B_{2}$ must each have two more neighbors, all of which must be different vertices, because if any two of them coincided, there would be a 4 or 5-length cycle in the graph, depending on whether the common neighbor is between $A_{1}$ and $A_{2}$, $B_{1}$ and $B_{2}$, or one is a neighbor of $A_{i}$ and the other of $B_{j}$ (Figure 1). This adds up to $4 \cdot 2 = 8$ more vertices, so the graph has at least $2 + 4 + 8 = 14$ vertices.

![](https://cdn.mathpix.com/cropped/2024_05_02_1872dd6038ffb907590bg-1.jpg?height=266&width=384&top_left_y=558&top_left_x=857)

Figure 1

A good 14-vertex graph exists, as shown in Figure 2. When selecting the neighbors of the last eight vertices $\left(A_{3}, A_{4}, A_{5}, A_{6}, B_{3}, B_{4}, B_{5}, B_{6}\right)$, it is important to ensure that the neighbors of the $A_{i}$ type vertices are all of the $B_{j}$ type, and one is a neighbor of $B_{1}$ and the other of $B_{2}$, and the same applies to the $B_{i}$ type vertices.

![](https://cdn.mathpix.com/cropped/2024_05_02_1872dd6038ffb907590bg-1.jpg?height=442&width=422&top_left_y=1129&top_left_x=838)

Remark. It can be shown that a 14-vertex graph that meets the conditions is unique up to isomorphism (thus, what we see in Figures 4 and 5 is essentially the same). This graph is called the Heawood graph, and its most famous construction is related to the Fano plane (about the Fano plane, see Tamás Schmidt: Geometric spaces from an algebraic perspective (KöMaL 2004/4, pp. 199-206)). The 7 points and 7 lines of the plane give the 14 vertices of the graph. Two vertices are connected by an edge if and only if one corresponds to a line and the other to a point on that line. Since there are 3 points on every line and 3 lines through every point in the plane, every vertex in the graph has degree 3. By the definition of the graph, it is bipartite (one class contains the vertices corresponding to the points of the plane, the other the vertices corresponding to the lines of the plane), so it has no odd-length cycles. There are no 4-length cycles in the graph, otherwise there would be two different points on the plane with two different connecting lines.

![](https://cdn.mathpix.com/cropped/2024_05_02_1872dd6038ffb907590bg-1.jpg?height=439&width=483&top_left_y=2084&top_left_x=802)

Figure 3
![](https://cdn.mathpix.com/cropped/2024_05_02_1872dd6038ffb907590bg-2.jpg?height=1152&width=526&top_left_y=125&top_left_x=780)