Actually the concept of Hamiltonian cycles is decidedly easier and less mathy than even basic algebra. At Kansas University the lowest level math class was called Topics, and one of the areas covered was graph theory, including Hamiltonian cycles. I don't recall anyone having problems with the concept, whereas the same group of kids would struggle to add fractions.
For P/NP examples, I find SAT the easiest to explain to people not in CS. It's just: there are some things that can be true or false, and some statements about them using and, or, and not. You want to find a set of T/F assignments that makes all those statements true. And it's intuitively obvious to people that it's much easier to check if an assignment is right than to find one.
Sure, any reasonably intelligent person can grasp what a Hamiltonian Cycle is, once you explain it to them. But this article starts talking about 'em before it's defined 'em, which is just bad pedagogy.
Sure, you don't have to know what it is to understand the rest of the article, but it's still a pretty valid criticism.
(I did three years of undergrad maths and I had to go look up what a Hamiltonian cycle is.)