Hamiltonian Graph Problem

369 Views Asked by At

I've been going about the proof of the Snark Graph's (https://en.wikipedia.org/wiki/Snark_(graph_theory)) non-Hamiltonicity. I understand that a snark is connected, bridgeless ( removing any edge does not make the graph unconnected), cubic ( $\forall\ v \in V(G), \deg(v) = 3),$ and a chromatic index of 4 ($\chi^\prime(G) = 4$).

I am having some issues synthesizing these properties to show there is at least two vertices without a Hamiltonian path in between them. Any assistance will be appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

Let's assume a snark has a Hamiltonian cycle. A snark has an even number of vertices (Handshaking lemma) so we can color the edges of the cycle red and blue. The edges that are not part of the cycle form a perfect matching. Color the edges of the perfect matching green. We have a 3-edge coloring of a snark, a contradiction.