Show that the Petersen graph does not contain any cycles of length $3$ or $4$.
I have been reading about how easy it is proved that the Petersen graph has no cycles of length 3 or 4 but I cannot seem to figure it out. I can see why it does not have a 3 or 4 cycle from a drawing but I was wondering if there is proof to it.
Proving this depends on how you define the Petersen graph.
Commonly, the Petersen graph is defined to have the subsets of $\{1,2,3,4,5\}$ having size 2 as vertices, with two vertices adjacent if the corresponding subsets are distinct.
In this model, a 3-cycle would be three vertices $\{a,b\}$, $\{c,d\}$, $\{e,f\}$ where $a,b,c,d,e,f \in \{1,2,3,4,5\}$, these three subsets are pairwise disjoint.
You should try to use a similar approach for a 4-cycle: what would it look like in terms of the definition of the vertex set? Can you argue that such a configuration is impossible from the definition of the vertices and their adjacencies?