Maximum number of highways

Question

There are 20 cities in a country, some of which have highways connecting them. Each highways goes from one city to another, both ways. There is no way to start in a city, drive along the highways of the country such that you travel through each city exactly once, and return to the same city you started in. What is the maximum number of roads this country could have?

Answer 1

What you want to determine is the number of edges a non-hamiltonian graph on $20$ vertices can have. The maximum is indeed $173$ highways.

Proof: consider a non-hamiltonian graph on $20$ vertices. It must have two non-adjacent vertices $v,w$ which have a sum of degrees less than $20$.(since otherwise it is hamiltonian by Ore's Theorem)

However if you remove $17$ edges from $K_{20}$ the sum of the degree of every pair $u,v$ of non-adjacent edges will be at least $20$.Notice before deleting any edges the sum of degrees of two adjacent vertices is $38$. When you delete the edge $uv$ you substract $2$ to the degree sum, but after that you substract at most $1$ to the degree sum with every edge, so you end up substracting at most $18$. Taking the degree down to at most $20$. So the graph satisfies Ore's condition and thus is hamiltonian.