Petersen graph has no cycle of length $7$

Question

Here is the solution which I am not getting, I am writing it in points along with the doubts I have (written in bold)-:

$1$ Suppose that the Petersen graph has a cycle C of length $7$.Since any two vertices of C are connected by a path of length at most $3$ on $C$ , any additional edge with endpoints on C would create a cycle of length at most $4$ Hence the third neighbor of each vertex on C is not on C.

$2$.Thus there are seven edges from $V \left(C\right) $ to the remaining three vertices.

$3$ By the pigeonhole principle, one of the remaining vertices receives at least three of these edges. This vertex x not on C has three neighbors on C.

$4$.For any three vertices on C, either two are adjacent or two have a common neighbor on C (again the pigeonhole principle applies). Using x, this completes a cycle of length at most 4. We have shown that the assumption of a $7$ cycle leads to a contradiction

In short I am not getting major of it .. I know it is duplicate of here please help me out !

Answer 1

For point $1$, Imagine the (hypothetical) $7-$cycle $C$ as a heptagon. The proposed "additional edge" is a diagonal of this heptagon. The statement is equivalent to saying that any such diagonal cuts the heptagon in to two pieces, one of which is a triangle or quadrilateral. Because the Petersen graph has no cycles of length $\lt5$, it means that the vertices in such a $C$ cannot be connected to each other except by the edges that are part of $C$.

Point $2$ follows directly from this and the fact that every vertex of the Petersen graph has degree $3$: since they each vertex in $C$ has $2$ edges in $C$, they must each have one that is not, and by point $1$, this edge must connect to a vertex not in $C$.

Point $3$ says that there is no way to connect the other ends of the $7$ edges mentioned in point $2$ to the three vertices not in $C$. This is because, after you've connected $2$ to each of them, you still have one left, which will be the third edge connected to whatever vertex you connect it to.

Point $4$ has two parts. The first says that given $3$ vertices $C$ of $C$, at least $2$ of them are connected by a path of length $\le2$ in $C$. This is because if one of them is $3$ edges away from both of the others, then the others are neighbors because $C$ is a cycle of length $7$. The second half simply says that, since point $3$ tells us that there is a vertex (call it $a$) not in $C$ connected to $3$ vertices in $C$, and (by the first part of $4$) $2$ of these are connected by a path of length $2$ in $C$, the edges connecting $a$ to those $2$ vertices along with the path connecting them in $C$ is a cycle of length $4$. $\square$

Answer 2

The Petersen graph is isomorphic to the Kneser graph $\text{KG}(5,2)$, hence we may assume that every vertex of the Petersen graph is labelled with a $2$-subset of $\{1,2,3,4,5\}$, and two vertices are joined by an edge if the corresponding subsets are disjoint. For instance,

$$\ldots\to(1,2)\to(4,5)\to(1,3)\to(2,5)\to(1,4)\to(2,3)\to(1,5)\to(3,4)\to\ldots $$ is a cycle with length $8$. Assume there is some cycle with length $7$. Without loss of generality (the Petersen graph is vertex-transitive) we may assume it is given by: $$\ldots\to(1,2)\to(?,?)\to(?,?)\to(?,?)\to(?,?)\to(?,?)\to(4,5)\to\ldots $$ Since $5<2\cdot 3$, the Petersen graph is triangle-free. Additionally, it is not difficult to prove there is no cycle with length $4$. Let $u,v,w$ the vertices not included in the previous cycle. Among $\{u,v,w\}$ there are at most two edges, but the neighbourhood of every vertex has cardinality $3$, so there are at least $7$ edges between $\{u,v,w\}$ and the vertices in the cycle. The pigeonhole principle then implies that there is a cycle with length $3$ or $4$, contradiction.

---

I will provide you a "spectral" alternative, too. Let $P$ be the adjacency matrix of $\text{KG}(5,2)$.
The diagonal elements of $P^m$ count the number of paths that starts at some vertex and return there in $m$ steps. We know in advance that the diagonal elements of $P^2$ equal three, the diagonal elements of $P,P^3$ equal zero and the diagonal elements of $P^4$ equal $15$. If we count the number of paths that start at some vertex and return there in $5$ steps ($12$), then compute $P^7$, we may easily check that there are no cycles with length $7$ in $\text{KG}(5,2)$.