In a script about graph theory is written that the graph has girth $5$ which is pretty easy to see. Anyway the proof is the following:
- no $1$ or $2$ circles
- $3$ circles: it has to exist $3$ in pairs disjoint sets of $2$ elements (do not exist)
- $4$ circles: can be shown by showing that the neighborhood of any pair of two non adjacent nodes has exactly one common neighbor
- $5$ cirlces: easy to see
My problem are the 3 circles, I don't know how to prove the argument. It is turning in my head and I can't solve it...
There is a nice trick here: the Petersen graph is a Kneser graph, precisely $\text{KG}(5,2)$, so the vertices can be seen as the $2$-subsets of $\{1,2,3,4,5\}$, connected through an edge iff they represent disjoint subsets. If there was a $3$-cycle in the Petersen graph, there would be $3$ mutually disjoint $2$-subsets of $\{1,2,3,4,5\}$, but that is clearly impossible since $5<6$.
In general, $\text{KG}(n,k)$ is triangle-free iff $n<3k$. Given Lovasz' theorem on the chromatic number of Kneser's graphs, $\chi(\text{KG}(n,k))=n-2k+2$, we have that there are triangle-free graphs with an arbitrarily large chromatic number. This fact is usually proved through Mycielski's construction, but there are many other interesting approaches.