Counter-Example to Diaby’s et al. Linear Programming Solution to the Traveling Salesman Problem

Abstract

The presented counter-example is a regular graph, and the aim was not to have an example with the least possible size; therefore, the focus was on clarity. The counter-example has, therefore, 366 nodes in two main clusters, each node (in the main part) having exactly four connections to other nodes in the cluster.