Suppose that $G$ is a graph with $pq$ vertices where $p$ and $q$ are primes and $2<p<q$.
If $(p-1)(q-1)$ vertices of $G$ have degree $p+q-1$ and all other vertices have degree $pq-1$, show that $G$ is not Hamiltonian.
I could just take $(p-1)(q-1)=\phi(pq)$ where $\phi$ is Euler-Totient Function.
But I dont know any conditions to show that a graph is Non-Hamiltonian?
Are there any way to show that a graph is Non-Hamiltonian?
Kindly help.
Let $A \subseteq V(G)$ be the set of vertices with degree $p+q-1$, and $B \subseteq V(G)$ be the set of vertices with degree $pq-1$. There are $pq - |A| = pq - (p-1)(q-1) = p+q+1$ vertices in $B$, and having degree $pq-1$ means that they're adjacent to every other vertex. As a result, each vertex in $A$ has $p+q-1$ neighbors in $B$, and cannot be adjacent to anything else.
Therefore, up to isomorphism, for every value of $p$ and $q$, there is only one graph of this type. For example, here is the graph for $p=3$ and $q=5$, with $A$ in red and $B$ in blue:
Now you should try to show that this graph is not Hamiltonian.
A common general approach is to check that a graph is not tough. A graph is tough when removing any $k$ vertices leaves at most $k$ connected components, and all Hamiltonian graphs are tough (though not all tough graphs are Hamiltonian).
You can also make the argument directly, without invoking toughness; just think about what a hypothetical Hamiltonian cycle would need to do in order to visit every vertex in $A$.