prove that Petersen graph has no cycles less than or equal to 4

Question

I studying the proof that the Petersen graph is not Hamiltonian, and in the proof, they used an observation that seems intuitively correct but I want to provide rigorous proof for it, given that I'm taking an introductory course to discrete mathematics.

Claim: Petersen graph has no cycles less than or equal to 4

I want to prove it by contradiction using the basics ideas, can you help me with that?

Answer 1

We can use a simple argument by coloring the edges of the Petersen's graph as shown below:

First note that there are 3 types of edges:

• 5 blue edges forming outer cycle of length 5
• 5 pink edges forming inner cycle of length 5
• 5 green edges connecting outer nodes with inner nodes

Now, since there is a blue cycle of length 5 with 5 outer blue nodes, it makes it impossible to have a blue monochrome cycle of length $\leq 4$, because

• for creating a length-4 or length-3 cycle we must connect two non-adjacent blue nodes by an additional blue edge.
• in order to accommodate that additional blue edge, we must remove an exisiting blue edge from the blue cycle.
• but, minimum number of blue edges needed to construct a length-5 blue cycle with 5 blue nodes is 5, with each node having one incoming and one outgoing blue edge.
• hence, we can't remove an edge from the existing length-5 blue cycle, which contains 5 blue edges only.

Using same argument we can show that we can't have an inner monochrome pink cycle of length $\leq 4$.

Also, a cycle which is not monochromatic must have a green edge (connecting an inner and an outer node). Now, in order to have a non-monochrome cycle of length $\leq 4$, we must have

• either a couple of green edges from a pink node, which is impossible (since there is exactly one green edge incident on each pink node),
• or a couple of green edges incident on a blue node (again impossible),
• or it would need at least one additional blue edge (connecting two non-adjacent blue nodes) or one additional pink edge (connecting two non-adjacent pink nodes), making it impossible to have blue or pink cycles of length 5.