  We present a matching and LP based heuristic algorithm that decides graph
non-Hamiltonicity. Each of the $n!$ Hamilton cycles in a complete directed
graph on $n+1$ vertices corresponds with each of the $n!$ $n$-permutation
matrices $P$, such that $p_{u,i}=1$ if and only if the $i^{th}$ arc in a cycle
enters vertex $u$, starting and ending at vertex $n+1$. A graph instance ($G$)
is initially coded as exclusion set $E$, whose members are pairs of components
of $P$, $\{p_{u,i} ,p_{v,i+1}\}, i=1,n-1$, for each arc $(u,v)$ not in $G$. For
each $\{p_{u,i} ,p_{v,i+1}\}\in E$, the set of $P$ satisfying
$p_{u,i}=p_{v,i+1}=1$ correspond with a set of cycles not in $G$. Accounting
for all arcs not in $G$, $E$ codes precisely the set of cycles not in $G$. A
doubly stochastic-like $\mathcal{O}$($n^4$) formulation of the Hamilton cycle
decision problem is then constructed. Each $\{p_{u,i} ,p_{v,j}\}$ is coded as
variable $q_{u,i,v,j}$ such that the set of integer extrema is the set of all
permutations. We model $G$ by setting each $q_{u,i,v,j}=0$ in correspondence
with each $\{p_{u,i} ,p_{v,j}\}\in E$ such that for non-Hamiltonian $G$,
integer solutions cannot exist. We recognize non-Hamiltonicity by iteratively
deducing additional $q_{u,i,v,j}$ that can be set zero and expanding $E$ until
the formulation becomes infeasible, in which case we recognize that no integer
solutions exists i.e. $G$ is decided non-Hamiltonian. Over 100 non-Hamiltonian
graphs (10 through 104 vertices) and 2000 randomized 31 vertex non-Hamiltonian
graphs are tested and correctly decided non-Hamiltonian. For Hamiltonian $G$,
the complement of $E$ provides information about covers of matchings, perhaps
useful in searching for cycles. We also present an example where the algorithm
fails to deduce any integral value for any $q_{u,i,v,j}$ i.e. $G$ is undecided.
