Quantitatively characterizing the failure of the converse of Dirac's theorem

Question

First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.

I am currently in a combinatorics and graph theory class and recently we have been studying Hamiltonian graphs. We have been discussing a few theorems characterizing these graphs. I am interested in Dirac's theorem which states

Dirac (1952) Let $G$ be a simple graph with $n \geq 3$ vertices such that for any vertex $v \in G$ we have $\deg(v) \geq \frac{n}{2}$. Then $G$ is Hamiltonian.

The converse is easily seen to be false. I am interested in understanding how often the converse fails. From my view, one way to make this precise is as follows. Let $H_n$ denote the set of Hamiltonian graphs on $n$-vertices. What can we say about the probability $$p_n = P(\deg(v) \geq \frac{n}{2},\forall v\in G \mid G \in H_n)$$

I am mainly interested in what happens as $n \to \infty$. For example, I think it might be interesting if Dirac's theorem becomes necessary and sufficient if we take $n$ large enough. One could also investigate analogous question for other theorems that give sufficient conditions for $G$ to be Hamiltonian (Ore's theorem, Posa's theorem). However, Dirac's seemed the simplest to investigate.

Is there any literature on questions resembling this?

Thanks.

Edit:

I have fixed my maple code and believe I now have the correct probabilities for $n=3,4,5,6,7,8,9$ computed:

• $p_3 = 1$
• $p_4 = 1$
• $p_5 = \frac{3}{8} = 0.375$
• $p_6 = \frac{19}{48} \approx 0.396$
• $p_7 = \frac{29}{383} \approx 0.075$
• $p_8 = \frac{106}{1549} \approx 0.068$
• $p_9 = \frac{1165}{177083} \approx 0.007$

So maybe $p_n \to 0$ as $n \to \infty$? Of course this is clearly not enough data to make any reasonable conjectures. Much more powerful computers than mine would likely be needed. Thanks everyone for the useful comments, I imagine this question could probably be closed.

Edit: One final comment, I think that regular graphs could be an important tool. Since it is clear that for a $k$-regular graph $G$ on $n$ vertices if $n$ is taken large enough then $G$ cannot satisfy Dirac's condition. Thus if one could show the existance of a subset of k-regular graphs $R_k \subset H_n$ that grows large as $n \to \infty$ this might force the set of graphs satisfying Dirac's condition to become small. This paper might be useful although I'm not familiar with applying analysis and probability to graph theory so I only have a cursory understanding of it.

Answer 1

The system has seen fit to bump this, so I'll throw in an answer.

As $n \to \infty$, the probability that a uniformly random graph is Hamiltonian is $1-o(1)$, and the probability that every vertex has degree greater than $n/2$ is $o(1)$ (roughly, the probability is about $1/2$ for each vertex), so a $o(1)$ fraction of Hamiltonian graphs on $n$ vertices have all degrees at least $n/2$.

If you weakened the condition to minimum degree $(1-\epsilon)n/2$ then almost all graphs meet it, so the weak converse would be true, but not for reasons that have anything to do with Hamiltonicity.

There's a more general point here about the difference between extremal and probabilistic results in graph theory. There shouldn't necessarily be any connection, but there's a reason why the same people tend to work on both types of problem. For example, we might say that Dirac's theorem (an extremal result) is morally true because at minimum degree $n/2$ every pair of vertices has a common neighbour, which allows us to do rotation-extension. The same phenomenon occurs at an edge density of $1/\sqrt n$ in random graphs, so we might guess that this is when graphs should become Hamiltonian. In fact, we know the real answer is much smaller; what we knew was a fact about our proof rather than the property of being Hamiltonian. So we could look at how we prove Hamiltonicity in $G_{n,p}$ at $p \approx \log n/n$ and see what property ensures Hamilton cycles in that case—information that we could bring back to the dense case to prove more results in that setting, and in turn suggest questions about random graphs, and so on forever.