Meredith graph

In the

Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian.^[4][5] However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.^[6]

The characteristic polynomial of the Meredith graph is ${\displaystyle (x-4)(x-1)^{10}x^{21}(x+1)^{11}(x+3)(x^{2}-13)(x^{6}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4}}$.

• 
  The

  chromatic number

  of the Meredith graph is 3.
• 
  The

  chromatic index

  of the Meredith graph is 5.