Existence of Hamiltonian Path using minimum and maximum degrees In a simple graph $G$ with $n$ nodes, let $c<\deg(V)<C \space \forall$ nodes $V$, for given constants $c<C<{n}$. Let the total number of edges in $G$ be $E$. What is the maximum value of $E$ for which there need not necessarily be a Hamiltonian path? Can we find any upper bounds for the same?
We can clearly see that $\frac{cn}{2} \leqslant E \leqslant \frac{Cn}{2}$. By Direc's theorem, if $c\geqslant\frac{n}{2}$, we can say for sure that the maximum value of $E$ is $\lceil\frac{cn}{2}\rceil$ since a Hamiltonian cycle is assured, thus giving a Hamiltonian Path.
However, I am not sure what to do in the case $c<\frac{n}{2}$. Any asymptotic expression or good upper bound for the maximum number of edges without a Hamiltonian path in the graph is welcome. Thank you in advance.
 A: If I understand correctly, your question is: for given $c, C$ and $n$ satisfying $c<C<n$, what is the maximal value of $E(c, C, n)$ such that there exists a graph on $n$ nodes with minimal degree $c$, maximal degree $C$, with $E(c, C, n)$ edges, and with no Hamiltonian path?
It is possible to construct a graph with $n\geq 2$ nodes, both the minimal degree $c$ and the maximal degree $C$ equal to $(1+\sqrt{4n-7})/2$ and with
$$
E:=(c^3 -2c^2+3c-2)/2 = n(\sqrt{4n-7}-1)/4
$$
edges, in which no Hamiltonian path exists.
Since $\frac{Cn}{2}$ (your upper bound from Dirac theorem) is in this case $n(\sqrt{4n-7}+1)/4$, the difference between $\frac{Cn}{2}$ and $E$ is
$$
\frac{Cn}{2} - E = \frac{n}{2},
$$
so it seems pretty close (linear in the number of nodes) to the optimal value that you are looking for.
The construction is as follows: take $c-1$ disjoint copies of $K_c - e$ (complete graph on $c$ nodes with one edge removed). Add two vertices, say $v$ and $w$. For every pair of nodes of degree $c-2$ in each of the cliques, add an edge between one of them and $v$, and an edge between the other one and $w$.
Taken from https://mathoverflow.net/a/242886 (an illustration can be found there).
Also, here are some papers in which sufficient conditions for traceability, in terms of minimum degree and some other parameters, are given:
Spectral radius and traceability of graphs with large minimum degree, here, and On minimum degree, leaf number, traceability and Hamiltonicity in graphs, to be found here. Finally, in this one a lower bound on the number of edges of maximal non-traceable graphs is given.
