% Note for production: after applying the journal settings, please run % LaTeX at least twice to resolve cross-references and hyperlinks. \documentclass[11pt,reqno]{amsart} \usepackage[cp1251]{inputenc} \usepackage[english,russian]{babel} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{graphicx} \pdfimageresolution=600 \usepackage{xcolor} \usepackage[colorlinks]{hyperref} \usepackage{microtype} \usepackage{calc} \usepackage{mathtools} \usepackage{cite} \usepackage{algorithm} \usepackage[noend]{algpseudocode} \usepackage{nccmath} \usepackage[active]{srcltx} \usepackage{titlesec} \titlespacing{\section}{0pt}{2.5ex}{1.5ex} \titlespacing{\subsection}{0pt}{1.5ex}{1ex} \titlespacing{\subsubsection}{0pt}{1.5ex}{1ex} \titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{} \titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }] \titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }] %%%%%---------- ORCiD \newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}} \def\udcs{519.174.2, 519.175.4} % çäåñü çàäàåòñÿ ÓÄÊ ñòàòüè \def\mscs{05C45, 05C80} % çäåñü çàäàåòñÿ êëàññèôèêàöèÿ AMS ñòàòüè \setcounter{page}{144} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{definition}{Definition} \newtheorem{corollary}{Corollary} \newtheorem{proposition}{Proposition} \newtheorem{remark}{Remark} \newtheorem{example}{Example} \hypersetup{linkcolor=blue,filecolor=black, urlcolor=blue,citecolor=blue} \def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}} \def\semrtop { \vbox{ \noindent\logo \hspace{-3mm} \parbox{12cm}{ \begin{center} {\LARGE \textsf{ÑÈÁÈÐÑÊÈÅ ÝËÅÊÒÐÎÍÍÛÅ}} \\[2mm] {\LARGE \textsf{ÌÀÒÅÌÀÒÈ×ÅÑÊÈÅ ÈÇÂÅÑÒÈß}} \\[2mm] {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm] {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm] \raisebox{1ex}{ISSN 1813-3304 } \vspace*{-3mm} % {\small Èíñòèòóò ìàòåìàòèêè èì. Ñ.Ë.Ñîáîëåâà ÑÎ ÐÀÍ}\\[-1mm] % {\small Sobolev Institute of Mathematics SB RAS} \end{center} } \vspace{-1mm} \noindent \begin{tabular}{c} \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\ \hline\hline \end{tabular} \vspace{3mm} {\flushleft\it Vol. 20, No. 2, pp. 144--145 (2026) \hspace{\fill}{\rm\small ÓÄÊ \udcs \hspace{-2mm}}} \newline %Volume, pages in Russian, filled by Editorial board {\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2026.20.???}}\hphantom{aaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs } }%\vbox } \begin{document} \renewcommand{\refname}{References} \renewcommand{\proofname}{Proof} \renewcommand{\figurename}{Fig.} \renewcommand{\thesection}{\arabic{section}.\hspace{-3mm}} %\renewcommand{\thesection}{\textcolor{blue}{\arabic{section}.}\hspace{-3mm}} \renewcommand{\algorithmicrequire}{\textbf{Input:}} \renewcommand{\algorithmicensure}{\textbf{Output:}} \newcommand{\skipwords}[1]{% \settowidth{\dimen0}{#1}% \hspace*{\dimen0}% } \thispagestyle{empty} \title[Ore-type Conditions and U-graphs.~I]{\large On $n$-vertex Hamiltonian Graphs.~I\\(Ore-type Conditions and U-graphs)} \author[T.I.~FEDORYAEVA]{{\bf T.I. FEDORYAEVA}\protect\orcidicon{0000-0002-5246-0522}} \address{Tatiana Ivanovna Fedoryaeva % Êîíòàêòíûå äàííûå âñåõ àâòîðîâ è ìåñòî ðàáîòû óêàçûâàþòñÿ òîëüêî íà àíãëèéñêîì ÿçûêå \newline\hphantom{iii} Sobolev Institute of Mathematics, \newline\hphantom{iii} pr. Koptyuga, 4, \newline\hphantom{iii} 630090, Novosibirsk, Russia}% \email{\textcolor{blue}{fti@math.nsc.ru}}% \thanks{\sc Fedoryaeva,~T.I., În $n$-vertex Hamiltonian graphs.~I~(Ore-type Conditions and U-graphs)} \thanks{\copyright \ 2026 Fedoryaeva,~T.I.} \thanks{\rm The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2026-0011)} \thanks{\it Received June, 15, 2026, published June, 15, 2026.}% \semrtop \vspace{1cm} \maketitle {\small \vspace{-12pt} \centerline{{\it Communicated by} {\sc P.P. Petrov} %({\it filled by Editorial board}) } \bigskip \begin{quote} \noindent{\bf Abstract:} {\fontsize{9pt}{11pt}\selectfont The Hamiltonian property of $n$-vertex graphs is studied both in the context of an axiomatic approach and in terms of classical sufficient conditions. It is known that almost all $n$-vertex graphs of small diameter $k=1,2,3$ are Hamiltonian \cite{fti24}. It turns out that classical sufficient Ore-type conditions for Hamiltonianity are not well adapted to identifying axiomatically rich classes of such $n$-vertex graphs and do not explain their Hamiltonian behavior. Therefore, in this paper, we introduce a new sufficient condition that defines the class of $U$-graphs based on the metric structure of spheres and the local independence number. We prove that every $U$-graph is Hamiltonian. Furthermore, almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are shown to be $U$-graphs sharing a unified mechanism for their Hamiltonian property. At the same time, numerous rich, especially exponentially large, classes of $U$-graphs of diameter $3$ and $4$ are explicitly constructed outside the known classical Ore-type conditions. Moreover, these well-known classes of Hamiltonian $n$-vertex graphs are rigorously established to be asymptotically small relative to $U$-graphs. Thus, for the study of the Hamiltonian property, the discovered condition proves to be more sensitive to the internal structure of graphs, demonstrating wide applicability from both the axiomatic and classical viewpoints. } \medskip \noindent{\bf Keywords:} graph, diameter, Hamiltonian graph, Hamiltonian\linebreak[4] cycle, typical graphs, almost all graphs. \end{quote} } \selectlanguage{english} \begin{hyphenrules}{english} \bigskip \section*{Introduction} \hspace*{\parindent} The Hamiltonian property of finite labeled simple $n$-vertex graphs of a given diameter is studied. For a connected graph $G=(V,E)$, {\it the distance} $\rho_G(u,v)$ between its vertices $u,v\in V$ is defined as the length of the shortest path connecting these vertices. In this case, $d(G)= \max_{u,v\in V} \rho_G(u,v)$ is {\it the diameter} of the graph $G$ and for a nonnegative integer $i$, $B_i^G(v)=\{u\in V\,|\,\rho_G(v,u)\leq i \}$ ($S_i^G(v)=\{u\in V|\,\rho_G(v,u)=i\}$) is {\it the ball of radius $i$} (is {\it the sphere of radius $i$}) centered at a vertex $v\in V$ in the metric space of the graph $G$ with the metric $\rho_G$. A cycle passing through every vertex of a graph exactly once is called {\it Hamiltonian}. A graph is {\it Hamiltonian} ({\it non-Hamiltonian}) if it contains (does not contain) a Hamiltonian cycle. Hamiltonicity is one of the central concepts of Graph Theory, also arising in various applied problems when it is required to detect the presence of a Hamiltonian cycle for a graph modeling the problem under consideration. The development of Hamiltonian graph research was driven both by natural practical problems and the simplicity of the theoretical formulation itself. This line of research dates back to the fundamental works of G.A.~Dirac in 1952 \cite{dirac} and O.~Ore in 1960 \cite{ore}. They were the first to propose very simple sufficient conditions for a graph to be Hamiltonian, thereby opening up this line of research, which is as complex as the problem statement itself is simple. As it turns out, the problem of deciding whether a graph is Hamiltonian is an $NP$-complete problem, and accordingly, one cannot expect a simple classification of graphs that have this property. To date, a huge number of results have been obtained in this area, and interest in this topic remains consistently high. The main course of research development and the results obtained on the topic of Hamiltonian graphs in various directions can be found in the surveys \cite{gould} and \cite{ush} and are certainly not exhausted by these sources. The complexity of the problem and the diversity of Hamiltonian graphs encountered also led to the development of an asymptotic or probabilistic approach to the study of Hamiltonicity, in particular, an approach conditioned by the concept of almost all. It is worth noting here the result of V.A.~Perepelitsa \cite{perepel} and J.W.~Moon \cite{Moon} on the Hamiltonian property of almost all $n$-vertex graphs. It is also well-known that almost all graphs have diameter $2$ \cite{Moon&Moser}. From this result of J.W.~Moon and L.~Moser, and Perepelitsa's Theorem, it is easy to obtain that almost all $n$-vertex graphs of diameter $2$ are Hamiltonian. In this regard, the question naturally arises about the Hamiltonian property of almost all $n$-vertex graphs of a fixed diameter $k$. This problem was posed by S.V.~Avgustinovich. In \cite{fti24}, the author established that almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are Hamiltonian, while almost all $n$-vertex graphs of fixed diameter $k\geq 4$ are non-Hamiltonian. This prompted the search for Hamiltonian conditions that identify asymptotically rich classes of $n$-vertex Hamiltonian graphs of small diameter (in particular, conditions ensuring that almost all such $n$-vertex graphs are Hamiltonian) and allow one to construct Hamiltonian cycles in such graphs quite efficiently. In the present paper, we define a new sufficient condition for a graph to be Hamiltonian and introduce the class of $n$-vertex $U$-graphs satisfying this condition. We prove their Hamiltonian property and examine them in the context of the stated asymptotic problem and the well-known classical Ore-type conditions. We establish that almost all graphs of fixed diameter $k=1,2,3$ are $U$-graphs, with the choice of $U$ being explicitly specified. We show that the classes of $n$-vertex graphs of small diameter ($k=3$ or $k=4$) satisfying the well-known classical Ore-type conditions are asymptotically small compared with the class of $U$-graphs. The earliest sufficient conditions obtained for Hamiltonicity were based on certain degree constraints for a graph; these were conditions requiring a large degree of the vertices themselves or a large degree sum of non-adjacent vertices. Although such an approach naturally limited the applicability of these conditions, it served as a driver for the subsequent emergence of new Ore-type conditions and the development of the entire theory of Hamiltonian graphs as a whole. Notice that in any graph $G$ of diameter $k\geq 3$, there arise disjoint spheres $S^G_1(u)$ and $S^G_1(v)$ of radius $1$ centered at diametral vertices: $$S^G_1(u)\cap S^G_1(v)=\varnothing.$$ Therefore, the sets $S^G_1(u)$, $S^G_1(v)$, $\{u\}$, and $\{v\}$ are pairwise disjoint. Consequently, $\deg_G u+\deg_G v\leq n-2$. This implies that the classical Dirac and Ore conditions are applicable for identifying Hamiltonicity only to graphs of diameter at most $2$. Subsequently, a number of authors continued to develop the Ore degree approach. Thus, H.A.~Jung \cite{jung} and, independently, C.~Nara \cite{nara} investigated graphs for which a weaker bound on the degree sum of non-adjacent vertices holds. They proved that for $n\geq 3$, every $2$-connected $n$-vertex graph for which the degree sum of any non-adjacent vertices is at least $n-1$ is either Hamiltonian or belongs to the following class of graphs: \begin{align}\label{34f} {\mathcal K}=\{ G \,|\,K_{p,p+1}\subseteq G \subseteq K_p + \overline{K}_{p+1} \mbox{ for a suitable } p\geq 2 \} \end{align} (here $+$ denotes the graph join operation). However, this approach also proves inapplicable, by the same arguments, to graphs of diameter at least $3$. In 1984, Fan strengthened the known results and showed that instead of requiring the degree condition for all pairs of non-adjacent vertices, it is sufficient to restrict attention to vertices at distance $2$. For $n\geq 3$, Fan proved the Hamiltonicity of a $2$-connected $n$-vertex graph satisfying the condition he introduced \cite{fan}: {\it Fan's Condition {\rm FC(G):} for any two vertices of an $n$-vertex graph $G$ at distance $2$, the degree of at least one of them is no less than $n/2$}. \noindent By considering only vertices at distance $2$ when analyzing the Hamiltonian property of a graph, Fan made a significant step toward shifting the focus in research from global graph properties to local ones, thereby extending the applicability of his sufficient condition. However, the technique employing his Ore-type condition FC(G) also fails to fully function for graphs of diameter $3$. It turned out that almost all $n$-vertex graphs $G$ of diameter $3$ are Hamiltonian and fail to satisfy {\rm FC(G)} (Theorem \ref{newtheorem10}). In 2006, A.S.~Asratian generalized the results of H.A.~Jung, C.~Nara, and several other authors (see \cite{asr}). To analyze graph Hamiltonicity, he utilized a technique related to the properties of metric balls of small radii and defined the following condition: {\it Asratian's Condition} AC(G): \noindent 1) {\it if a vertex $w$ is adjacent to each of the non-adjacent vertices $u$ and $v$ of a graph $G$, then $\deg_G u + \deg_G v \geq |B_2^G(w)|-1$}; \noindent 2) {\it the subgraph induced by the ball $B_2^G(w)$ is $2$-connected for every vertex $w$}. For $n\geq 3$, Asratian proved that a connected $n$-vertex graph $G$ satisfying AC(G) is either Hamiltonian or belongs to the class ${\mathcal K}$ (defined in \eqref{34f}). It is easy to see that every graph in the class ${\mathcal K}$ has diameter $2$. At the same time, the approach proposed by Asratian also proved effective for graphs of diameter greater than 2. His paper provides examples of such Hamiltonian graphs of any predefined diameter \cite{asr}. Nevertheless, the applicability of Asratian's Condition to graphs of diameter $3$ also turns out to be insufficient: it yields only an asymptotically small class of graphs satisfying AC(G). Namely, in the present paper, it is analogously proved that almost all $n$-vertex graphs $G$ of diameter $3$ are Hamiltonian and fail to satisfy AC(G) (Theorem \ref{newtheorem50}). Another direction of research into Hamiltonicity was related to the concept of the degree of a set of vertices, which naturally generalized the definition of the classical degree of a graph vertex (for details, see survey \cite{gould}). In \cite{fgjl}, utilizing a new approach and essentially a condition on the degree of two-element vertex sets, R.J.~Faudree, R.J.~Gould, M.S.~Jacobson, and L.M.~Lesniak proved, for all sufficiently large $n$, the Hamiltonicity of a $2$-connected $n$-vertex graph satisfying the condition they introduced: {\it Condition of R.J.~Faudree, R.J.~Gould, M.S.~Jacobson, L.M.~Lesniak}. FGJLC(G): {\it $|S_1^G(u)\cup S_1^G(v)|\geq n/2$ for any two distinct vertices $u,v$ of an $n$-vertex graph $G$}. \noindent In Theorem \ref{newtheorem40}, it is proved that this Ore-type condition FGJLC(G) (the only one known to the author) already defines an asymptotically complete class of Hamiltonian $n$-vertex graphs $G$ of diameter $3$. At the same time, as established in Theorem \ref{700t}, there exist numerous rich, especially exponentially large, classes of $U$-graphs $G$ of diameter $3$ that do not satisfy FGJLC(G). In addition, exponentially large classes of $n$-vertex $U$-graphs of diameter $4$ that do not satisfy {\rm FGJLC(G)} are constructed (Theorem~10). Theorem~10 demonstrates that the $U$-condition is not a specialized tool intended solely for graphs of diameter $3$. Although almost all graphs of fixed diameter $k\geq 4$ are non-Hamiltonian, the $U$-graph condition no longer describes a typical behavior; instead, it characterizes a large number of rich, likewise exponential, subclasses of Hamiltonian graphs of diameter $4$ that do not satisfy {\rm FGJLC(G)}. Moreover, for graphs of diameter $4$, the picture changes radically: the class of $2$-connected $n$-vertex FGJLC-graphs is established to be asymptotically small relative to these $U$-graphs (Theorems 11 and 12). Furthermore, for $2$-connected graphs of diameter $4$ satisfying either Fan's condition FC(G) or Asratian's condition AC(G), a similar $o$-behavior holds as in the case of diameter $3$: their number is also asymptotically small compared to that of these $U$-graphs (Theorems 13 and 14). The paper is organized as follows. It consists of two parts: Part I comprises Sections 1--5, and Part II comprises Sections 6--10. All necessary definitions and notations are introduced in the Introduction and Section~1. Section~1 also presents the required preliminary results and proves some combinatorial assertions used throughout the paper. In Section~2, the concept of a $U$-graph is defined. It is proved that every $U$-graph is Hamiltonian (Theorem \ref{1m}); remarkably, the proof of Hamiltonianity is constructive. In Section~3, typical graphs of small diameter are studied in connection with the Hamiltonian property. Based on the class ${\mathcal H}_{n,k,\Delta}$ of typical graphs of diameter $k\geq 3$ previously introduced by the author \cite{fti24}, a new class ${\mathcal H^*}_{n,3,\Delta}$ of typical $n$-vertex graphs of diameter $3$ is constructed (Theorem \ref{t1b}). In addition, a class of typical $n$-vertex graphs with a pre-forbidden cut is established (Theorem \ref{6033nn}). Here, we employ the well-known Matula bound for the clique number and the Moon--Moser theorem on graphs of diameter $2$. Theorem \ref{6033nn}, in particular, yields a class ${\mathcal H^*}_{n,2,\Delta}$ of typical graphs of diameter $2$ with the required properties (Corollary \ref{906t}), and is also subsequently used in the study of graphs of diameter $4$. Further, using the constructed classes ${\mathcal H^*}_{n,k,\Delta}$ for $k=2,3$, we prove that almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are $U$-graphs, where the set $U$ consists of a pair of diametral vertices (Theorem \ref{57m}). In Section~4, we consider classical Ore-type conditions for Hamiltonianity. Using Shearer's Combinatorial Lemma (see Section 1), we prove that almost all $n$-vertex graphs $G$ of diameter $3$ fail to satisfy both Fan's condition FC(G) and Asratian's condition AC(G) (Theorems \ref{newtheorem10} and \ref{newtheorem50}). We further establish that almost all graphs of diameter $3$ satisfy FGJLC(G) (Theorem \ref{newtheorem40}), using in the proof the new class ${\mathcal H^*}_{n,3,\Delta}$ of constructed typical $n$-vertex graphs for an appropriate value of $\Delta$ (see Section~3). Thus, almost all graphs of diameter $3$ are $U$-graphs and FGJLC-graphs. At the same time, this section explicitly constructs numerous rich, namely exponentially large, classes ${\mathcal K}_{n,3,\varepsilon}$ of $n$-vertex $U$-graphs of diameter $3$ that do not satisfy FGJLC(G) (Theorem \ref{700t}). Moreover, in the constructed graphs, the FGJLC(G) condition is violated both on pairs of vertices from $U$ and on pairs of vertices from $V\setminus U$. Section $5$ summarizes the first part of the paper. The second part of the paper continues the study of $U$-graphs and the Ore-type conditions for graphs of diameter $4$ \cite{fti26-2}. As with diameter $3$, exponentially large classes ${\mathcal K}_{n,4,\varepsilon}$ of $n$-vertex $U$-graphs of diameter $4$ that do not satisfy FGJLC(G) are constructed, exhibiting two types of violations of this condition (Theorem 10). Moreover, it turns out that in the case of diameter $4$, the picture changes radically for FGJLC-graphs. Namely, an upper bound for the number of $2$-connected $n$-vertex FGJLC-graphs is first found (Theorem 11). Next, a class ${\mathcal K}_{n,4,\Delta,\varepsilon}$ of $n$-vertex $U$-graphs of diameter $4$ that do not satisfy FGJLC(G) is constructed, and their asymptotically exact number is established (Theorem 12). It turns out that $2$-connected FGJLC-graphs of diameter $4$ constitute an asymptotically small fraction of the $U$-graphs in the class ${\mathcal K}_{n,4,\Delta,\varepsilon}$ (Theorem 12). At the same time, for $2$-connected graphs of diameter $4$ satisfying either Fan's condition FC(G) or Asratian's condition AC(G), a similar $o$-behavior holds as in the case of diameter $3$: their number is also asymptotically small compared to that of these $U$-graphs (Theorems 13 and 14). Moreover, explicit upper bounds are obtained for the number of such $n$-vertex graphs with these Ore-type conditions. \section{Preliminary information} \hspace*{\parindent} The article uses the generally accepted concepts and notation of graph theory \cite{emel90, xar69}, as well as the standard concepts of combinatorial analysis \cite{grah94}. We consider only finite simple (i.e.,\/ without loops and multiple edges) graphs $G=(V, E)$ with set of vertices $V=\{1,2,\ldots,n\}$, $n\in {\mathbb N}$. As usual, denote by $G\setminus v$ the graph obtained as a result of {\it removing a vertex} $v$ and all edges incident to it, $G\setminus V'$ is the graph obtained by removing all vertices from a subset $V'\subseteq V$, $\overline{G}$ --- {\it complement} of graph $G$, $G[V']$ is the subgraph induced by the subset $V'\subseteq V$, $K_n$ --- {\it a complete} $n$-vertex graph, $K_{n,m}$ --- {\it a complete bipartite} graph; a set $S\subseteq V$ is {\it an independence set} of graph $G$ if all vertices in $S$ are pairwise non-adjacent in $G$, $\alpha(G)$ --- {\it independence number} of graph $G$, $\deg_G v$ --- {\it the degree of a vertex $v$}. For a path $P$ with endpoints $v_0$ and $v_n$, sequentially passing through vertices $v_0, v_1,\ldots, v_n$, the notation $P=(v_0, v_1, \ldots, v_n)$ is used. In addition, for the part of a path $P$ between its vertices $u$ and $v$ (including these vertices themselves) the notation $P(u,v)$ is used. A shortest path of length $d(G)$ is called {\it the diametral path} of the graph $G$, and by {\it a pair of diametral vertices} we mean an unordered pair of two vertices from the set $V$, the distance between which is equal to the diameter. Let $A,B\subseteq V$ and $A\cap B=\varnothing$. In what follows, we shall use the following notation for sets of edges with endpoints in $V$: $$E(A,B)=\{\{u,v\}\,| \,u\in A,\,v\in B\},$$ $$E(A,A)=\{\{u,v\}\,| \,u,v\in A \mbox{ and } u\neq v \}.$$ For the graph $G=(V,E)$ under consideration, we shall also use the notation $E_G(A,B)=E\cap E(A,B)$. We shall write $\lceil x \rceil$ ($\lfloor x \rfloor$) to denote the smallest (largest) integer greater (less) or equal to a real nonnegative number $x$. To denote {\it the asymptotic equality} of functions $f(n)$ and $g(n)$ as $n \rightarrow \infty$, we use the notation $ f(n)\sim g(n)$, which by definition means that $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=1$ or, equivalently, $f(n) = g(n)(1+r(n))$ for all sufficiently large $n$, where $r(n) = o(1)$ is {\it the approximation error} of $g(n)$. In what follows, we shall use the following well-known combinatorial identities for binomial coefficients. \begin{equation}\label{1s} \binom{n-m}{2}=\binom{n}{2}-nm+\frac{m(m+1)}{2},\,m\leq n; \end{equation} \begin{equation}\label{2s} \binom{n}{2} +\binom{m}{2}=\binom{n+m}{2} - mn. \end{equation} We shall use the following estimate for truncated weighted binomial sums, which shows that such sums are exponentially small after the natural normalization. \begin{lemma}[truncated sums of weighted binomial coefficients \cite{fti22}] \label{0r} Let $q$ and $\Delta$ be fixed, $q\geq 1$, and $0<\Delta<1$. Then there exists $\varepsilon(q,\Delta)$, independent of $n$, such that $0<\varepsilon(q,\Delta)<1$ and the following asymptotic equality holds as $n\to\infty$ $$ \Bigl(\frac{q}{q+1}\Bigr)^n \sum_{s=0}^{\left\lfloor\frac{n}{q+1}\Delta\right\rfloor} \binom{n}{s}q^{-s} =\varepsilon^n(q,\Delta)\sqrt{n}\,O(1), $$ where $$ \varepsilon(q,\Delta) =q\Delta^{-\frac{\Delta}{q+1}} (q+1-\Delta)^{-\frac{q+1-\Delta}{q+1}} q^{-\frac{\Delta}{q+1}}. $$ \end{lemma} We shall also need the widely known Shearer's Lemma. We use its combinatorial version (see, for example, \cite[Lemma~2.9, p.~6]{galvin}), which allows one to estimate the size of a family of subsets via the sizes of its projections as follows. A family $\mathcal K\subseteq 2^X$ may be regarded as a collection of objects, each of which is determined by a choice of elements from $X$. Under projection onto $L\subseteq X$, only the part $K\cap L$ remains from each object $K\in{\mathcal K}$, and the whole projection of the family consists of all such possible traces and is denoted by $\operatorname{tr}_L(\mathcal K)=\{K\cap L: K\in{\mathcal K}\}.$ The lemma states that if each coordinate $x\in X$ participates in at least $t$ projections, then the collection of these projections already controls the size of the whole family ${\mathcal K}$. We now give the formal statement of the combinatorial version of Shearer's Lemma. \begin{lemma}[Combinatorial Shearer's Lemma]\label{Shearer} Let $X$ be a finite set, let $t$ be a positive integer, and let ${\mathcal L}$ be a finite multiset of subsets of $X$ such that every element $x\in X$ belongs to at least $t$ members of ${\mathcal L}$, counted with multiplicities. Then, for every ${\mathcal K}\subseteq 2^X$, the following inequality holds $$|{\mathcal K}|^t \leq \prod_{L\in {\mathcal L}}\bigl|{\mathrm{tr}}_L({\mathcal K})\bigr|,$$ where ${\mathrm{tr}}_L({\mathcal K})=\{K\cap L \,|\, K\in {\mathcal K}\}$, and the product over $L$ is taken with account of the multiplicities of the elements of the multiset ${\mathcal L}$. \end{lemma} The following simple combinatorial lemma will be used to estimate traces of families of sets on sets of edges incident to a prescribed vertex. \begin{lemma}\label{newlemma11} Let $A$ be an $n$-element set, let $k>\frac{n}{2}>0$, and let ${\mathcal A}_{k,n}=\{B \,| \,B\subseteq A \mbox{ and } |B|\geq k\}$. Then $|{\mathcal A}_{k,n}|\leq 2^{n-1}.$ \end{lemma} \begin{proof} Since $n>0$, we have $A\neq\varnothing$. Partition all subsets of $A$ into pairs of the form $\{B,A\setminus B\}$, where $B\subseteq A$. The number of such pairs is $2^{n-1}$. Moreover, in each pair one set has at least $n/2$ elements and the other has at most $n/2$ elements. It remains to note that each such pair contains at most one set from ${\mathcal A}_{k,n}$. \end{proof} To estimate the size of a class of graphs with a certain property, the concept of {\it almost all} is often used; in this approach, the studied property is considered for graphs with a large number of vertices. Let ${\mathcal J}_n$ be the class of labeled $n$-vertex graphs with the fixed set of vertices $V=\{1,2,\ldots,n\}$, $n\in {\mathbb N}$. Consider some property ${\mathcal P}$, which each graph may or may not possess. Denote by ${\mathcal J}^{\mathcal P}_n$ the set of all graphs from ${\mathcal J}_n$ that possess the property ${\mathcal P}$. {\it Almost all graphs possess the property} ${\mathcal P}$ if $\lim_{n\rightarrow \infty} |{\mathcal J}^{\mathcal P}_n|/|{\mathcal J}_n|=1$, \/i.e.\/ $|{\mathcal J}^{\mathcal P}_n| \sim |{\mathcal J}_n|$, and {\it there are almost no graphs with the property} ${\mathcal P}$, if $\lim_{n\rightarrow \infty} |{\mathcal J}^{\mathcal P}_n|/|{\mathcal J}_n|=0.$ When studying almost all graphs in a given class, it is often useful not merely to formulate characteristic properties, but to distinguish directly a subclass of typical graphs (in \cite{fti15,fti16}, a more general concept of a class of typical combinatorial objects for a given class of objects admitting the concept of dimension is formulated, further we will also use this formal concept for graphs when the dimension of a graph is understood as the number of its vertices). Let $\Omega $ be an arbitrary class of graphs such that $\Omega_n\neq\varnothing$ for all large enough $n$, where $\Omega_n=\Omega\,\cap\, {\mathcal J}_n$. A subclass $\Omega^{\ast}\subseteq \Omega$ is {\it the class of typical graphs of the class} $\Omega$ if $\lim_{n\rightarrow \infty}\,|\Omega_n^{\ast}|/|\Omega_n|=1.$ A property of graphs of the class under consideration is \/{\it typical}\/ if almost all graphs of this class have this property. Let ${\mathcal J}_{n,\,d=k}$, ${\mathcal J}_{n,\,d\geq k}$, ${\mathcal J}^{\ast}_{n,\,d\geq k}$ be the following classes of labeled $n$-vertex graphs: graphs of diameter $k$; connected graphs of diameter at least $k$; graphs (not necessarily connected) containing a geodesic path of length at least $k$, respectively. In \cite{fti17}, it is proved that all three classes of graphs ${\mathcal J}_{n,\,d=k}$, ${\mathcal J}_{n,\,d\geq k}$, ${\mathcal J}^{\ast}_{n,\,d\geq k}$ have the same asymptotic cardinality for $k\geq 3$, and asymptotically exact value $2^{\binom{n}{2}}\,\xi_{n,k}$ of the number of graphs in these classes is found. Here $$\xi_{n,k}=q_k\,\,(n)_{k-1}\, \Bigr(\frac{3}{2^{k-1}}\Bigl)^{n-k+1},\,\,\,\, q_k=\frac{1}{2}\,(k-2)\,2^{-\binom{k-1}{2}}, $$ $(n)_k=n(n-1)\cdots (n-k+1)$, $(n)_0=(0)_0=1$ and $(n)_k=0$ if $n|V(G)|+\alpha_G(u,v)$ if $u,v\in V(G)\setminus U$ and $u\neq v$, where $\alpha_G(u,v)$ is the independence number of the subgraph of $G$ induced by the set $V(G)\setminus (B_1^G(u)\cup B_1^G(v))$; {\rm (ii)} $|S_1^G(u)|>|U|$ if $u\in U$. \end{definition} \renewcommand{\thedefinition}{\arabic{definition}} \noindent In what follows, for a graph $G$ under consideration, when its subset of vertices is not specified explicitly, we shall also use the term {\it $U$-graph} if, for some subset $U\subseteq V(G)$, properties (i) and (ii) of the above definition are satisfied. We emphasize that this definition is not formulated in terms of any special properties of a typical subclass of the graphs under consideration, but is formalized directly in terms of the metric structure of the graph itself, the properties of its spheres, and the local independence number. For example, the parameter $\Delta$, which will be used below in constructing typical classes of graphs of given diameter, is not involved in the definition of a $U$-graph (it appears later only when verifying that graphs of certain typical classes satisfy the $U$-graph condition). \begin{theorem}[sufficient condition for Hamiltonian graph]\label{1m} Every U-graph is Hamiltonian and the construction of its Hamiltonian cycle is given in the proof. \end{theorem} \begin{proof} Let $G$ be a $U$-graph for some subset of vertices $U \subseteq V(G)$. Let us assume that $|V(G)|=2$. From condition {\rm (i)} on $U$ it is easy to understand that $U\neq\varnothing$. Then $|S_1^G(u)|\geq 2$ and $u\not\in S_1^G(u)$, where $u\in U$. We have arrived at a contradiction. Hence $|V(G)|\geq 3$. Further, $G$ is a connected graph, therefore every limit simple path of graph $G$ contains at least three vertices. For further exposition, we introduce the following series of concepts and notations for the vertices of an arbitrary fixed simple path $P$ of graph $G$ with endpoints $u,v$. The vertex $w\in V(P)$ will be called $u$-{\it vertex}\/ if $wu\in E(G)$ and $wv\not\in E(G)$; $v$-{\it vertex}\/ if $wv\in E(G)$ and $wu\not\in E(G)$; $uv$-{\it vertex}\/ if $wu, wv\in E(G)$; $o$-{\it vertex}\/ if $wu\not\in E(G)$ and $wv\not\in E(G)$. In this case, we denote by $\alpha_u, \alpha_v, \alpha_{uv}, \alpha_0$ the number of $u$-vertices, $v$-vertices, $uv$-vertices and $o$-vertices respectively. Note that vertex $u$ (vertex $v$) is the $v$-vertex (the $u$-vertex) if $uv\in E(G)$ and the $o$-vertex if $uv\not\in E(G)$. We call $uv$-vertices $uv$-{\it neighboring}\/ if there are no $uv$-vertices between them on the path $P$. Additionally, $uv$-{\it interval} is a part of the path $P$, limited by $uv$-neighboring $uv$-vertices, including these vertices. Further for the proof we will need the following lemma. \begin{lemma}\label{lemma55a} Let $P$ be a limit simple path of graph $G$ and the conditions of Theorem {\rm\ref{1m}} are fulfilled. Then in the graph $G$ either there exists a simple cycle $C$ such that $V(C)=V(P)$, or $V(P)\varsubsetneq V(P')$ for some limit simple path $P'$. \end{lemma} \begin{proof} Let $u,v$ are endpoints of path $P$. Since P is a limit simple path, we obtain \begin{equation}\label{20p} S_1^G(u)\cup S_1^G(v)\subseteq V(P) \end{equation} \noindent and \begin{equation}\label{21p} \begin{gathered} \alpha_u=|S_1^G(u)\setminus S_1^G(v)|,\ \alpha_v=|S_1^G(v)\setminus S_1^G(u)|,\\ \alpha_{uv}=|S_1^G(u)\cap S_1^G(v)|,\\ \alpha_0=|V(P)\setminus (S_1^G(u)\cup S_1^G(v))|. \end{gathered} \end{equation} By Lemma \ref{lemma2a} we further assume that $G$ does not contain cross-end $uv$-edges for path $P$. Consider three possible cases. {\it Case} 1: $uv\in E(G)$. In this case path $P$ and edge $uv$ form the required cycle $C$. {\it Case} 2: $uv\not\in E(G)$ and $u,v\not\in U$. Consider $uv$-intervals and show that each such interval contains at least one $o$-vertex. Note that all $uv$-intervals have length no less than 2, otherwise there will be cross-end $uv$-edges. Suppose on the contrary that there is an $uv$-interval with endpoints $w_1,w_2$ such that $P(w_1,w_2)$ does not contain $o$-vertices (without loss of generality, we assume that $w_1$ lies on path $P$ between vertices $u$ and $w_2$). Then each of its internal vertices (different from $w_1$ and $w_2$) is either a $u$-vertex or a $v$-vertex. Let $z_1,z_2,\ldots,z_m$ be all the internal vertices of path $P(w_1,w_2)$ during the sequential transition along path $P$ from $w_1$ to $w_2$ (see Fig.\ref{fig8}). \begin{figure}[h] \centering \vspace{-1.5mm} \includegraphics[scale=1.3]{4-2026} \vspace{-2.0mm} \caption{}\label{fig8} \end{figure} Note that $z_1$ is not a $u$-vertex, otherwise there are cross-end $uv$-edges $uz_1,w_1v$. Therefore, $z_1$ is a $v$-vertex. Further, if $z_2$ is a $u$-vertex, then there are also cross-end $uv$-edges $uz_2,z_1v$. Hence, $z_2$ is a $v$-vertex. Continuing to move from the vertex $z_i$ to $z_{i+1}$, we obtain that $z_m$ is a $v$-vertex. This means that $uw_2,z_mv$ are cross-end edges. We have arrived at a contradiction. \begin{figure}[h] \centering \vspace{-2.0mm} \includegraphics[scale=0.9]{5-2026} \vspace{-2.0mm} \caption{}\label{fig10} \end{figure} Now let us find out the structure of the vertex types of $uv$-intervals with a single $o$-vertex. Let $w_1,w_2$ be $uv$-neighboring $uv$-vertices and $w_0$ be the only $o$-vertex from the $uv$-interval between these vertices, where $w_1$ lies between the vertices $u$ and $w_2$ on path $P$. Consider all vertices $z_1,z_2,\ldots,z_m$ in a sequential transition along path $P$ from $w_1$ to $w_0$, not including $w_1,w_0$. In graph $G$ there is no edge $uz_1$, since $w_1$ is a $uv$-vertex and there are no cross-end $uv$-edges. Therefore, $z_1$ is a $v$-vertex. Further, continuing to move from vertex $z_i$ to $z_{i+1}$, we obtain that $z_2,\ldots,z_m$ are $v$-vertices. Similarly, moving from vertex $w_2$ to vertex $w_0$ along the path $P$, it is proved that all internal vertices from $P(w_0,w_2)$ are $u$-vertices (see Fig.\ref{fig10}). Thus, every $uv$-interval with a single $o$-vertex $w_0$ contains vertices $w_0^-$ and $w_0^+$ adjacent to $w_0$ on the path $P$ such that either $w_0^-\in P(u,w_0)$ and $w_0^-$ is a $v$-vertex, or $w_0^-=w_1$, and either $w_0^+\in P(w_0,v)$ and $w_0^+$ is an $u$-vertex, or $w_0^+=w_2$. Denote by $S(G)$ the set of all $o$-vertices belonging to $uv$-intervals with a single $o$-vertex. Estimate the number $|S(G)|$. Let $\alpha_1,\alpha_2$ be the number of $uv$-intervals with a single $o$-vertex and with at least two $o$-vertices, respectively. Using relations \eqref{20p} and \eqref{21p}, we obtain \begin{equation}\label{22p} \alpha_0\geq \alpha_1+2\alpha_2+2, \end{equation} \begin{equation}\label{23p} \alpha_1+\alpha_2\geq\alpha_{uv}-1, \end{equation} \begin{equation}\label{24p} |V(G)|\geq |V(P)|\geq \alpha_u+\alpha_{uv}+\alpha_v+\alpha_0. \end{equation} From \eqref{21p}-\eqref{24p} follows the inequality $|V(G)|\geq |S_1^G(u)\cup S_1^G(v)| +\alpha_1 + 2\alpha_2 + 2 \geq |S_1^G(u)\cup S_1^G(v)|+|S_1^G(u)\cap S_1^G(v)|+\alpha_2+1$. Hence, \begin{equation}\label{25p} \alpha_2\leq |V(G)|-|S_1^G(u)\cup S_1^G(v)|-|S_1^G(u)\cap S_1^G(v)|-1. \end{equation} Finally, from \eqref{23p}, \eqref{25p} and condition $u,v\not\in U$ we conclude \begin{eqnarray*} |S(G)|&=& \alpha_1\geq |S_1^G(u)\cap S_1^G(v)|-1-\alpha_2\\ &\geq & |S_1^G(u)\cup S_1^G(v)|+2|S_1^G(u)\cap S_1^G(v)|-|V(G)|> \alpha_G(u,v). \end{eqnarray*} Moreover, $S(G)\subseteq V(G)\setminus (B_1^G(u)\cup B_1^G(v))$. Therefore, $S(G)$ is not an independent set in the subgraph induced by the set $V(G)\setminus (B_1^G(u)\cup B_1^G(v))$, and hence contains adjacent $o$-vertices $w_1,w_2\in S(G)$. Then, as proved above, the vertices $w_1^-,w_1^+,w_2^-,w_2^+$ are defined (see Fig.\ref{fig22p}). \begin{figure}[h] \centering \vspace{-2.0mm} \includegraphics[scale=0.9]{6-2026} \vspace{-2.0mm} \caption{}\label{fig22p} \end{figure} Thus, for suitable indices $i$ and $j$, $C=(u,w_i^+,w_j^-,v,w_j^+,w_j,w_i,w_i^-,u)$ is a simple cycle of graph $G$ such that $V(C)=V(P)$ (see Fig.\ref{fig22p}). {\it Case} 3: $uv\not\in E(G)$ and at least one of the vertices $u,v$ belongs to set $U$. \noindent Let, for example, $u\in U$. Due to \eqref{20p} and the relation $u\not\in S_1^G(u)$, for each vertex $w\in S_1^G(u)$ there exists a {\it vertex-predecessor} $w'\in V(P)$ on path $P$ such that $w',w$ are adjacent vertices and $w'\in P(u,w)$ ($w'$ does not coincide with $v$ and may coincide with $u$). By $Pr(S_1^G(u))$ we denote the set of vertex-predecessors of all vertices from $S_1^G(u)$. It is obvious that $|Pr(S_1^G(u))|=|S_1^G(u)|$. By virtue of the condition on $U$, there exists a vertex-predecessor $w'_u\in Pr(S_1^G(u))\setminus U$ and its corresponding vertex $w_u\in S_1^G(u)$ adjacent to $w'_u$. Note that $w'_u\neq u$ (since $u\in U$) and $w'_u\neq v$ as a predecessor (see Fig.\ref{fig40a}a). \begin{figure}[h] \centering \vspace{-2.0mm} \includegraphics[scale=1]{7-2026} \vspace{-2.0mm} \caption{}\label{fig40a} \end{figure} In addition, due to the absence of cross-end $uv$-edges in $G$ there is no edge $w'_uv$. Thus, we found a simple path $P_u=(w'_u,u,w_u,v)$ such that $V(P_u)=V(P), w'_u\not\in U$ and $w'_u v\not\in E(G)$ (see Fig.\ref{fig40a}a). Further, we can assume that the vertex $w'_u$ is $P_u$-limit, otherwise there exists a limit simple path $P'_u$ such that $V(P_u)\varsubsetneq V(P'_u)$ and the second conclusion of the lemma holds. Thus, $P_u$ is a limit simple path. If $v\not\in U$, we come to the conditions of case 2 for path $P_u$. Therefore, we further assume that $v\in U$. Repeating the reasoning of case 3 for vertex $v$ (similarly as for $u$), we obtain a limit simple path $P_{uv}=(w'_v,v,w_v,w'_u)$ (see Fig.\ref{fig40a}b) such that $w'_v,w'_u\not\in U, w'_v\neq w'_u$ and $V(P_{uv})=V(P_u)$. It remains to note that for path $P_{uv}$ we come to the considered case 1 if $w'_uw'_v\in E(G)$, otherwise to case 2. \end{proof} Let us continue the proof of Theorem \ref{1m}. Let $P$ be a simple path of graph $G$ of greatest length. By Lemma \ref{lemma55a}, there exists a simple cycle $C$ such that $V(C)=V(P)$. It remains to apply Corollary \ref{cor1a}. \end{proof} Note that any independent set of the subgraph induced by the set $V(G)\setminus (B_1^G(u)\cup B_1^G(v))$ can be enlarged by adding $u$ to an independent set of the graph $G$. \begin{remark} For any vertices $u,v\in V(G)$, the inequality $\alpha(G)>\alpha_G(u,v)$ holds. \end{remark} \noindent Therefore, for property (i) in the definition of a $U$-graph, it is sufficient that the required inequality hold for the "global"\/ independence number $\alpha(G)$ of the whole graph instead of the "local"\/ number $\alpha_G(u,v)$ for each pair of vertices. \begin{remark} For an $n$-vertex $U$-graph, the inequalities $n\geq 3$ and $0\leq |U|\leq n-2$ hold. \end{remark} We now prove that the diameter of every $U$-graph is bounded; namely, the following proposition holds. \begin{proposition} The diameter of a $U$-graph does not exceed $4$. \end{proposition} \begin{proof} We prove two properties of any $n$-vertex $U$-graph $G$. 1) For each vertex $u\in U$ there exists a vertex $u'\notin U$ adjacent to $u$. Indeed, it is enough to note that property (ii) in the definition of a $U$-graph implies $S^G_1(u)\setminus U\neq \varnothing$. 2) If $v_1,v_2\notin U$, then $\rho_G(v_1,v_2)\leq 2$. Indeed, we may assume that $v_1\neq v_2$. By property (i) in the definition of a $U$-graph, we obtain $$n+2|S_1^G(v_1)\cap S_1^G(v_2)|\!\geq\! |S_1^G(v_1)\cup S_1^G(v_2)|+2|S_1^G(v_1)\cap S_1^G(v_2)| \!\!>\!\! n+\alpha_G(v_1,v_2).$$ \noindent Hence, $|S_1^G(v_1)\cap S_1^G(v_2)|> \alpha_G(v_1,v_2)/2$. Therefore, $\rho_G(v_1,v_2)\leq 2$. Using these properties, we now estimate the distance between arbitrary vertices of the graph $G$. If $u_1,u_2\in U$, then $\rho_G(u_1,u_2)\leq\rho_G(u_1,u'_1)+\rho_G(u'_1,u'_2)+\rho_G(u'_2,u_2) \leq 4$ by properties $1$ and $2$. In the case $u\in U$, $v\notin U$ we similarly obtain $\rho_G(u,v) \leq \rho_G(u,u')+\rho_G(u',v)\leq 3$. It remains to consider the case $v_1,v_2\notin U$, which follows directly from property $2$. \end{proof} \section{Hamiltonian property of typical graphs of small diameter} In \cite{fti24}, it was proved that almost all graphs of diameter $k=1,2,3$ are Hamiltonian, and the class ${\mathcal H}_{n,k,\Delta}$ of typical graphs of diameter $k$, each of which has a Hamiltonian cycle, was constructed (Lemma \ref{l7l}). In this section, we first define a new class ${\mathcal H^*}_{n,k,\Delta}$ of typical graphs of small diameter $k$ whose graphs satisfy the sufficient conditions of Theorem \ref{1m}. The case $k=1$ is trivial. For the complete $n$-vertex graph $K_n$, $n\geq 3$, we have $\alpha(K_n)=1$, $|S_1^G(u)\cup S_1^G(v)|=n$, $|S_1^G(u)\cap S_1^G(v)|=n-2$ and $|S_1^G(u)|=n-1$ for any distinct vertices $u,v$. Therefore, for $n\geq 3$, $K_n$ is a $U$-graph for every subset $U\subset V(K_n)$ with at most $n-2$ vertices; in particular, when $U$ consists of a pair of diametral vertices. We now consider graphs of diameter $k=3$ and define a subclass \begin{equation}\label{25q} {\mathcal H^*}_{n,3,\Delta}\subseteq {\mathcal H}_{\!n,3,\Delta}. \end{equation} \noindent Class ${\mathcal H}_{n,3,\Delta}$ is the union of the subclasses ${\mathcal H}_{n,3,\Delta}(x,y)$ over all different $x,y\in V$, and $x,y$ is the unique pair of diametral vertices of every graph from ${\mathcal H}_{n,3,\Delta}(x,y)$. By ${\mathcal H^*}_{n,3,\Delta}(x,y)$ we denote the class of graphs $F\in {\mathcal H}_{n,3,\Delta}(x,y)$ for which the following two properties $e^*$) and $g$) hold. $e^*$) Property of spheres intersections: \begin{align*} |S_1^F(u) \cap S_1^F(v)| > \frac{n}{4}\Delta \;\; \forall u,v\in V\setminus \{x,y\} \mbox{ and } u\neq v;\\ |S_1^F(u) \cap S_1^F(z)| >\frac{n}{6}\Delta \;\; \forall u\in V\setminus\{x,y\}\;\; \forall z\in \{x,y\}. \end{align*} g) Property of spheres differences: \begin{align*} |S_1^F(u) \setminus S_1^F(v)| > \frac{n}{4}\Delta \;\; \forall u,v\in V\setminus\{x,y\} \mbox{ and } u\neq v;\\ |S_1^F(u) \setminus S_1^F(z)| > \frac{n}{3}\Delta \;\; \forall u\in V\setminus\{x,y\}\;\; \forall z\in \{x,y\};\\ |S_1^F(z)\setminus S_1^F(u)| > \frac{n}{6}\Delta \;\; \forall u\in V\setminus\{x,y\}\;\; \forall z\in \{x,y\}. \end{align*} \noindent Put $${\mathcal H^*}_{n,3,\Delta}=\bigcup\limits_{x\neq y} {\mathcal H^*}_{n,3,\Delta}(x,y).$$ Thus, graphs of the class ${\mathcal H^*}_{n,3,\Delta}$ possess properties a), b), c), d), $e^*$), f), g) (for fixed distinct vertices $x$ and $y$). We now estimate $|{\mathcal H^*}_{n,3,\Delta}|$. Let $x,y,u,v$ be different elements of $V$ and $0<\Delta<1$. Define the following classes \begin{eqnarray*} && H_{n,\Delta,u}(x,y,u,v)=\{G\in {\mathcal J}_n | B_1^G(x)\cap B_1^G(y)\!=\!\varnothing, \,|S_1^G(u)\setminus S_1^G(v)|\!\leq \! \frac{n}{4}\Delta\},\\ && H_{n,\Delta,uv}(x,y,u,v)=\!\{G\in {\mathcal J}_n | B_1^G(x)\cap B_1^G(y)\!=\!\varnothing, |S_1^G(u)\cap S_1^G(v)| \!\leq \!\frac{n}{4}\Delta\},\\ && H_{n,\Delta,u}(x,y,u)=\{G\in {\mathcal J}_n | B_1^G(x)\cap B_1^G(y)=\varnothing, \,|S_1^G(u)\setminus S_1^G(x)|\leq \frac{n}{3}\Delta\},\\ && H_{n,\Delta,x}(x,y,u)=\{G\in {\mathcal J}_n \,|\, B_1^G(x)\cap B_1^G(y)=\varnothing, \, |S_1^G(x)\setminus S_1^G(u)|\!\leq \!\frac{n}{6}\Delta\},\\ && H_{n,\Delta,xu}(x,y,u)=\{G\in {\mathcal J}_n | B_1^G(x)\cap B_1^G(y)=\varnothing, \,|S_1^G(u)\cap S_1^G(x)|\!\leq \!\frac{n}{6}\Delta\}. \end{eqnarray*} Estimate the number of graphs in these classes. \begin{lemma}\label{lemma1r} Let $x,y,u,v$ be different vertices of $V$, $\Delta$ does not depend on $n$ and $0<\Delta<1$. Then the following estimates hold as $n\rightarrow \infty$ \begin{eqnarray*} &&|H_{n,\Delta,uv}(x,y,u,v)|=a_n\,\varepsilon^n(3,\Delta)\sqrt{n}\,O(1),\\ &&|H_{n,\Delta,u}(x,y,u,v)|=a_n\,\varepsilon^n(3,\Delta)\sqrt{n}\,O(1). \end{eqnarray*} \end{lemma} \begin{proof} Consider the indices $i,j$ and $s$, which will correspond to the number of vertices in $S_1^G(u)\setminus (S_1^G(v)\cup \{v\}), S_1^G(v)\setminus (S_1^G(u)\cup \{u\})$ and $S_1^G(u)\cap S_1^G(v)$, respectively. Estimate the number $|H_{n,\Delta,uv}(x,y,u,v)|$. It is easy to understand that all graphs of class $H_{n,\Delta,uv}(x,y,u,v)$ are contained among graphs $G$ constructed as follows: 1) connect vertices $u,v$ with an edge or they will be non-adjacent, there are 2 possibilities; 2) choose an $s$-element subset $V_{uv}\subseteq V\setminus \{u,v\}$, $0\leq s\leq \lfloor\frac{n}{4}\Delta\rfloor$ (note $\lfloor\frac{n}{4}\Delta\rfloor \frac{3n}{4}\Delta\mbox{ and } |S_1^G(u)\cap S_1^G(v)|>\frac{n}{4}\Delta; \end{equation} \begin{equation}\label{99N} |S^G_1(w)|=|S^G_1(w)\setminus S^G_1(u)|+ |S^G_1(w)\cap S^G_1(u)|> \frac{n}{3}\Delta > 2=|U|. \end{equation} Now condition (ii) for the U-graph follows from \eqref{99N}. Further, taking into account \eqref{98N} and the property of the cardinality of independence sets, we conclude that the graph $G$ also satisfies the required condition (i). \end{proof} In the case of graphs of diameter $2$, an assertion analogous to Proposition \ref{33m} also holds when the set $U$ consists of a pair of diametral vertices. Moreover, as will be shown in Proposition \ref{3m} below, this is true even for every set of vertices $U\subset V$ of cardinality at most $2\,n/5$. To prove this fact, we need to define a class of typical $n$-vertex graphs of diameter $2$ with the required properties. We shall consider a more general problem of constructing typical graphs for certain classes of graphs. This general setting will allow us to use these typical graphs both for graphs of diameter 2 in this section and later for graphs of diameter 4. Let $A,B,C$ be a partition of an $n$-element vertex set $V$, where the cases $A=\varnothing$ and $B=\varnothing$ are allowed. Let $0<\sigma<1$ be independent of $n$, and let $|C|\geq \sigma n$. Denote by ${\mathcal G}_n(A,B;\sigma)$ the family of all graphs $H$ on the vertex set $V$ for which $E_H(A,B)=\varnothing$. Obviously, ${\mathcal G}_n(\varnothing,\varnothing;\sigma)={\mathcal J}_n$. In what follows, for such fixed subsets $A,B,C$, we shall use the notation $$a=|A|,\,\, b=|B|, \,\, c=|C|.$$ Then $$|{\mathcal G}_n(A,B;\sigma)|=2^{\binom{n}{2}-ab}.$$ Let $0<\Delta<1$ be fixed. Define a subclass $${\mathcal H}_{n,\Delta,\cap,\setminus}(A,B)\subseteq {\mathcal G}_n(A,B;\sigma),$$ consisting of all graphs $H\in {\mathcal G}_n(A,B;\sigma)$ such that, for any distinct vertices $u,v\in V$, the following conditions hold \begin{equation}\label{2000mm} |S_1^H(u)\cap S_1^H(v)\cap C|> \frac{c}{4}\Delta; \end{equation} \begin{equation}\label{2001mm} |(S_1^H(u)\setminus S_1^H(v))\cap C|> \frac{c}{4}\Delta. \end{equation} Next, put $$ {\mathcal H}_{n,\alpha}(A,B)= \left\{H\in {\mathcal G}_n(A,B;\sigma)\,|\, \alpha(H)\frac{n}{4}\Delta\geq 1.$$ Consequently, $H$ contains non-adjacent vertices. \end{proof} \begin{corollary}\label{r1} For all $n\geq \frac{4}{\sigma \Delta}$, the following inclusions hold $${\mathcal H}_{n,\Delta,\cap,\setminus}(A,B)\subseteq {\mathcal J}_{n,d=2},\,\,\,{\mathcal H^*}_{n,2,\Delta}(A,B)\subseteq {\mathcal J}_{n,d=2}.$$ \end{corollary} We now estimate the number of graphs that do not satisfy conditions \eqref{2000mm}, \eqref{2001mm}. \begin{lemma}\label{600nn} Let $A,B,C$ be a partition of an $n$-element set $V$, and let $|C|\geq \sigma n$, where $0<\sigma<1$ is independent of $n$. Then, for every fixed $0<\Delta<1$, $$ \left| {\mathcal G}_n(A,B;\sigma)\setminus {\mathcal H}_{n,\Delta,\cap,\setminus}(A,B) \right| =2^{\tbinom{n}{2}-ab}\,\,\Psi(n)\,O(1)=o(|{\mathcal G}_n(A,B;\sigma)|),$$ where $\Psi(n)=\varepsilon^{\sigma n}(3,\Delta^*) \, n(n-1)\sqrt{n}$ and $\Delta^*$ is an arbitrary constant such that $\Delta<\Delta^*<1$. \end{lemma} \begin{proof} Fix an ordered pair of distinct vertices $u,v\in V$ and introduce the notation: $C^*=C\setminus\{u,v\}$ and $c^*=|C^*|$. Then $n\geq c\geq c^*\geq c-2 \geq \sigma n -2.$ Therefore, for all sufficiently large $n$, we have $c\Delta/4 \leq (c^*+2)\Delta/4 \leq c^*\Delta^*/4.$ Note that for a graph $H\in {\mathcal G}_n(A,B;\sigma)$ for which condition \eqref{2000mm} is violated at the vertices $u$ and $v$, the inequality $|S_1^H(u)\cap S_1^H(v)\cap C|\leq \frac{c}{4}\Delta$ holds. Denote the number of such graphs by $h_{n,uv}(A,B)$. It is easy to see that all such graphs are contained among graphs $G$ constructed as follows: 1) Define the adjacency of the vertices $u$ and $v$ with vertices of the set $C^*$. Choose $s$ vertices from $C^*$ and join each of them by an edge to both $u$ and $v$, where $s\leq \left\lfloor {c^*\Delta^*/4}\right\rfloor$. From the remaining $c^*-s$ vertices, choose $i$ vertices and join them only to the vertex $u$. Next, from the remaining $c^*-s-i$ vertices of $C^*$, choose $j$ vertices and join them only to the vertex $v$. 2) On $V$, define an $n$-vertex graph $G$ for which $E_G(A,B)=\varnothing$ and the adjacency between the vertices of the sets $\{u,v\}$ and $C^*$ is prescribed. There are $2^{\binom {n}{2}-ab-2c^*}$ choices. Thus, using Lemma \ref{0r} on truncated sums of weighted binomial coefficients with parameter $q=3$, we obtain \begin{eqnarray*} h_{n,uv}(A,B) &\leq& \sum\limits_{s=0}^{\lfloor c^*\Delta^*/4\rfloor}\!\tbinom{c^*}{s} \!\sum\limits_{i=0} ^{c^*-s}\tbinom{c^*-s}{i}\!\sum\limits_{j=0} ^{c^*-s-i}\!\!\tbinom{c^*-s-i}{j}2^{\tbinom{n}{2}-ab-2c^*}\\ &=& 2^{\tbinom{n}{2}-ab}\Bigr(\frac{3}{4}\Bigl)^{\!c^*}\,\sum\limits_{s=0}^{\lfloor c^*\Delta^*/4 \rfloor} \tbinom{c^*}{s} \,3^{-s}\\ &=& 2^{\tbinom{n}{2}-ab}\,\,\varepsilon^{c^*}(3,\Delta^*) \, \sqrt{c^*} \,O(1)\\ &=& 2^{\tbinom{n}{2}-ab}\,\,\varepsilon^{\sigma n}(3,\Delta^*) \,\sqrt{n} \,O(1). \end{eqnarray*} We now consider condition \eqref{2001mm}. The way of specifying the adjacency of the vertices of the set $\{u,v\}$ with vertices of $C^*$ is completely identical to that considered above for condition \eqref{2000mm}. Only in this case, when estimating the number of graphs, the outer summation is taken over the index responsible for the number of vertices in the difference of spheres. Therefore, the same arguments show that the number of graphs for which $|(S_1^H(u)\setminus S_1^H(v))\cap C|\leq \frac{c}{4}\Delta,$ is also $2^{\tbinom{n}{2}-ab}\,\,\varepsilon^{\sigma n}(3,\Delta^*) \,\sqrt{n} \,O(1)$. Since there are $n(n-1)$ ordered pairs of distinct vertices, the number of graphs in the class ${\mathcal G}_n(A,B;\sigma)$ in which at least one of conditions \eqref{2000mm} or \eqref{2001mm} is violated for at least one pair $u$ and $v$ is $2^{\tbinom{n}{2}-ab}\,\,\Psi(n)\,O(1).$ \end{proof} We now consider the condition on the independence number. \begin{lemma}\label{601nn} Let $A,B,C$ be a partition of an $n$-element set $V$, and let $|C|\geq \sigma n$, where $0<\sigma<1$ is independent of $n$. Then there exists a positive infinitesimal function $\Phi_\sigma(n)$, independent of the choice of $A,B,C$, such that $$ \left| {\mathcal G}_n(A,B;\sigma)\setminus {\mathcal H}_{n,\alpha}(A,B) \right| \leq 2^{\binom{n}{2}-ab}\,\Phi_\sigma(n)=o(|{\mathcal G}_n(A,B;\sigma)|). $$ \end{lemma} \begin{proof} The classical estimate for the independence number of almost all $m$-vertex graphs is well known. The estimate $\alpha (H) < \lfloor 2 \log_2 m\rfloor$ itself follows directly, for example, from Matula's estimate for the clique number of a random graph \cite[Lemma~1, p.~366]{Matula}, applied to the complement of the graph. Consider the class $H_{m,\alpha\geq}=\{H\in {\mathcal J}_m\, |\, \alpha(H)\geq \left\lfloor 2\log_2(m)\right\rfloor\}$, and denote by $\phi_m$ the proportion of such $m$-vertex graphs. Then $$\phi_m = \frac{|H_{m,\alpha\geq}|}{|{\mathcal J}_m|} \,\, \xrightarrow[\substack{m \to \infty}]{} 0.$$ For each fixed $\sigma >0$, define the function $$\Phi_{\sigma}(n)=\sup_{m\geq \sigma n}\phi_m.$$ Obviously, $\Phi_{\sigma}(n)$ is a positive infinitesimal function as $n$ tends to infinity. Moreover, from the inequality $n-a\geq \sigma n$, we obtain $$\phi_{n-a}\leq \Phi_{\sigma}(n).$$ Note that if $G\in {\mathcal G}_n(A,B;\sigma)\setminus {\mathcal H}_{n,\alpha}(A,B)$, then $G[V\setminus A]\in H_{n-a,\alpha\geq}$; otherwise, we would have $\alpha(G)\leq \alpha(G[A])+\alpha(G[V\setminus A]) < a+ \left\lfloor 2\log_2(n-a)\right\rfloor$. It is now easy to see that all graphs of the class ${\mathcal G}_n(A,B;\sigma)\setminus {\mathcal H}_{n,\alpha}(A,B)$ are contained among graphs $G$ constructed as follows: 1) On the $a$-element set, define an arbitrary graph. There are $2^{\binom{a}{2}}$ choices. 2) Define the edges between the vertices of the sets $A$ and $C$; there are $2^{ac}$ choices. 3) On the set $V\setminus A$, specify a graph from the class $H_{n-a,\alpha\geq}$. Thus, we obtain \begin{eqnarray*} |{\mathcal G}_n(A,B;\sigma)\setminus {\mathcal H}_{n,\alpha}(A,B)| &\leq& 2^{\binom{a}{2}}\,2^{ac}\, |H_{n-a,\alpha\geq}|\\ &=& 2^{\binom{a}{2}}\,2^{ac}\, 2^{\binom{n-a}{2}} \phi_{n-a}\\ &\leq& 2^{\binom{n}{2}-ab} \Phi_{\sigma}(n) \end{eqnarray*} \end{proof} \begin{theorem}\label{6033nn} Let $A,B,C$ be a partition of an $n$-element set $V$, and let $|C|\geq \sigma n$, where $0<\sigma<1$ is independent of $n$. Then, for every fixed $0<\Delta<1$, ${\mathcal H^*}_{n,2,\Delta}(A,B)$ is a class of typical $n$-vertex graphs in the class ${\mathcal G}_n(A,B;\sigma)$; in particular, $$\left| {\mathcal H^*}_{n,2,\Delta}(A,B) \right| =\left(1-o(1)\right)2^{\binom{n}{2}-ab}.$$ \end{theorem} \begin{proof} By Lemmas \ref{600nn} and \ref{601nn}, ${\mathcal H}_{n,\Delta,\cap,\setminus}(A,B)$ and ${\mathcal H}_{n,\alpha}(A,B)$ are classes of typical $n$-vertex graphs in the class ${\mathcal G}_n(A,B;\sigma)$. It remains to note that the intersection of typical classes of a given class is also a typical class of this class. \end{proof} \begin{remark}\label{yyy} The remainder $o(1)$ in Theorem~{\rm\ref{6033nn}} is independent of the choice of $A,B,C$ for fixed $\sigma,\Delta$. \end{remark} We note two particular cases. If $|A|$ is bounded, $|B|$ has linear order in $n$, and $|C|\geq \sigma n$, then Theorem \ref{6033nn} gives a typical class of graphs on $V$ with the prescribed forbidden cut $E(A,B)=\varnothing$. This form will be used later in the construction of a class of $U$-graphs of diameter $4$ (see Part II \cite{fti26-2}). We now consider the case $A=B=\varnothing$. Put $${\mathcal H^*}_{\!n,2,\Delta}={\mathcal H^*}_{n,2,\Delta}(\varnothing,\varnothing).$$ \noindent By Corollary \ref{r1}, for all sufficiently large $n$, ${\mathcal H^*}_{\!n,2,\Delta}\subseteq{\mathcal J}_{n,d=2}$. Thus \({\mathcal H^*}_{\!n,2,\Delta}\) is a class of $n$-vertex graphs of diameter $2$ satisfying Property of spheres intersections and differences, and Property of cardinality of their independent sets. It is also well known that almost all $n$-vertex graphs have diameter 2 \cite{Moon&Moser}. Directly from this fact, Theorem \ref{6033nn}, and Corollary \ref{r1}, we obtain the following corollary. \begin{corollary}\label{906t} ${\mathcal H^*}_{\!n,2,\Delta}$ is a class of typical $n$-vertex graphs {\rm(}typical $n$-vertex graphs of diameter $2${\rm)}. \end{corollary} \begin{proposition}\label{3m} Almost all $n$-vertex graphs {\rm(}graphs of diameter $2${\rm)} are $U$-graphs for every $U\subset V$ such that $|U|<2\, n/5$. \end{proposition} \begin{proof} By virtue of Corollary \ref{906t}, it is sufficient to prove that for a suitable value of $\Delta$ and all large enough $n$, all graphs of class ${\mathcal H^*}_{\!n,2,\Delta}$ are $U$-graphs for every $U\subset V$ such that $|U|<2\, n/5$. Further, the verification of the properties of a $U$-graph (with a preliminary choice of the constant $\Delta$) is completely identical to the proof of Proposition \ref{33m}. \end{proof} The following Theorem follows directly from Propositions \ref{33m}, \ref{3m} and the case of graphs of diameter $k=1$ considered above. \begin{theorem}\label{57m} Almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are $U$-graphs, where the set $U$ consists of a pair of diametrical vertices. \end{theorem} The following assertion, previously obtained by the author in \cite{fti24}, follows directly from Theorems \ref{1m} and \ref{57m}. { \renewcommand{\thecorollary}{\arabic{corollary} {\rm\cite{fti24}}} \begin{corollary}\label{60a} Almost all graphs of fixed diameter $k=1,2,3$ are Hamiltonian graphs. \end{corollary} } Thus, the sufficient condition for Hamiltonicity introduced here turns out to be "ubiquitous": it holds for almost all graphs of small diameter and confirms both the common character of Hamiltonicity and the unified choice of the vertex set $U$ for each class of graphs of fixed diameter $k=1,2,3$. For $k=1$, this condition holds trivially; for $k=2$, it follows from the typical properties of intersections and differences of graph spheres and from the smallness of the independence number; and for $k=3$, it follows from the structure and properties of the newly constructed typical graphs of diameter~$3$. \section{Ore-type conditions and $U$-graphs of diameter $3$}\label{section4} In this section, in the context of the asymptotic problem under consideration (see the Introduction), we study a number of Ore-type conditions and the introduced $U$-graphs. As noted in the Introduction, the simple observation on the existence of disjoint spheres in graphs of diameter greater than $2$ implies that the classical conditions of Dirac, Ore, Jung, Nara, and similar conditions cannot be used for such graphs. We now turn to the sufficient condition FC(G), proposed by Fan. Although FC(G) is applicable to graphs of large diameter, the proportion of $n$-vertex Hamiltonian graphs of diameter $3$ satisfying this condition turns out to be asymptotically small. \begin{theorem}\label{newtheorem10} Almost all $n$-vertex graphs $G$ of diameter $3$ are Hamiltonian and do not satisfy {\rm FC(G)}. \end{theorem} To prove Theorem \ref{newtheorem10}, we shall need the following lemma on the number of graphs with a set of vertices of large degree. Let $Q\subseteq V$. Denote by ${\mathcal G}(V,Q,k)$ the family of all graphs $H$ on the set $V$ such that $\deg_H u\geq k$ for every vertex $u\in Q$. \begin{lemma}[Graphs with large degrees on a prescribed subset]\label{newL900} Let $V$ be an $n$-element vertex set, let $Q\subseteq V$, $|Q|=q\geq 1$, and let $k>(n-1)/2.$ Then $$|{\mathcal G}(V,Q,k)|\leq 2^{\binom{n}{2}-q/2}.$$ \end{lemma} \begin{proof} We may assume that $n\geq 2$ (otherwise $n=1$, $V=Q$, ${\mathcal G}(V,Q,k)=\varnothing$, and the required estimate is obvious). We count the number of ways to choose the edges of a graph $H\in {\mathcal G}(V,Q,k)$. Let $W=V\setminus Q$ and $s=|W|$. Then $s=n-q$, and there are obviously $2^{\binom{s}{2}}$ choices for the edges with endpoints in $W$. We count the number of choices for the remaining edges incident to vertices from $Q$. Define the following set of edges $$X=E(Q,Q)\cup E(Q,W).$$ To construct a graph $H$, it remains to choose edges from the set $X$ so that the resulting graph belongs to the class ${\mathcal G}(V,Q,k)$. For $u\in Q$, define $E_u=\{e\in X\,|\, e \mbox{ incident to }u\}$ and consider the multiset ${\mathcal L}=\{E_u \,|\, u\in Q\}\ \cup\ \{\{e\} \,|\, e\in E(Q,W)\}.$ Then every edge $e=\{u,v\}$ from $X$ is covered at least twice: if $u,v\in Q$, then $e\in E_u \cap E_v$, while in the case $u\in Q$ and $v\in W$, we obviously have $e\in E_u \cap \{e\}$. Consider the family ${\mathcal K}\subseteq 2^X$ of all sets of edges $E\subseteq X$ for which, in the graph $(V,E)$, every vertex $u\in Q$ has degree at least $k$. Then $|E\cap E_u|\geq k$. Taking into account the relations $|E_u|=n-1$, $k>|E_u|/2$, and Lemma \ref{newlemma11}, we have $$\bigl|{\mathrm{tr}}_{E_u}({\mathcal K})\bigr|\leq |{\mathcal A}_{k,|E_u|}|\leq 2^{|E_u|-1}=2^{n-2}.$$ It is also easy to see that $\bigl|\mathrm{tr}_{\{e\}}(\mathcal K)\bigr|\leq 2.$ Now, from Combinatorial Shearer's Lemma \ref{Shearer} with $t=2$, we obtain \begin{eqnarray*} |{\mathcal K}|^2 &\leq& \prod_{L\in {\mathcal L}}\bigl|{\mathrm{tr}}_L({\mathcal K})\bigr| = \prod_{u\in Q}\bigl|{\mathrm{tr}}_{E_u}({\mathcal K})\bigr|\,\, \prod_{e\in E(Q,W)}\bigl|{\mathrm{tr}}_{\{e\}}({\mathcal K})\bigr| \\ &\leq& (2^{n-2})^q \, 2^{qs}=2^{2\bigl (\binom{q}{2} + qs\bigr)-q}. \end{eqnarray*} \noindent Thus, taking into account the binomial identity \eqref{2s}, we conclude $$|{\mathcal G}(V,Q,k)|\leq 2^{\binom{s}{2}}\,|{\mathcal K}|\leq 2^{\binom{s}{2}+ \binom{q}{2} + qs - q/2} =2^{\binom{n}{2}-q/2}.$$ \end{proof} We now consider the class ${\mathcal FC}_{n,3}$ of all $n$-vertex graphs $G$ of diameter $3$ with a unique pair of diametral vertices and satisfying FC(G). We estimate the number of such graphs. \begin{lemma}\label{newlemma400} $|{\mathcal FC}_{n,3}|\leq 2^{\binom{n}{2}} \frac{1}{2}\,n(n-1) \Bigl(\frac{1+ \sqrt{2}}{4}\Bigr)^{n-2}.$ \end{lemma} \begin{proof} Let $F\in {\mathcal FC}_{n,3}$, and let $x$, $y$ be diametral vertices of the graph $F$. Since $S_1^F(x)\cap S_1^F(y)=\varnothing$, we have $\deg_F x \, + \, \deg_F y\leq n-2.$ Therefore, we may assume that $\deg_F x < n/2$. Consider the stratification of the graph $F$ by distance from the vertex $x$. Let $V_i=\{v\in V(F)\,|\, \rho_F(x,v)=i \}$, $i=0,1,2,3$, and let $a=|V_1|$, $b=|V_2|$. Then $V_0=\{x\}$, $V_3=\{y\}$ and $a < n/2$, $a+b=n-2$. In addition, by FC(G), we obtain $\deg_F u \geq n/2$ if $u\in V_2$. Let $F^*=F\setminus \{x,y\}$ and $k=\lceil n/2 \rceil - 1$. Then $\deg_{F^*} u \geq k >(n-3)/2$ for every vertex $u\in V_2$. It is now easy to see that graphs with the properties described above are contained among graphs constructed as follows. 1) Choose an ordered pair of distinct vertices $x,y\in V$; there are $n(n-1)$ choices. 2) Choose an $a$-element set $V_1\subseteq V\setminus \{x,y\}$. There are $\binom{n-2}{a}$ choices, where $1 \leq a < n/2$. Join $x$ by an edge to each vertex of $V_1$. 3) Define the $b$-element set $V_2=V\setminus (V_1\cup \{x,y\})$, $b=n-2-a$. 4) Choose a nonempty set $V_y\subseteq V_2$. There are at most $2^b$ choices. Join $y$ by an edge to each vertex of $V_y$. 5) On the $(n-2)$-vertex set $V\setminus\{x,y\}$, define a graph from the class ${\mathcal G}(V\setminus\{x,y\},V_2,k)$. Thus, using Lemma \ref{newL900}, Newton's Binomial Theorem, and the combinatorial identity \eqref{1s}, we conclude \begin{eqnarray*} |{\mathcal FC}_{n,3}| &\leq& \sum_{1 \leq a < n/2} n(n-1) \tbinom{n-2}{a} \, 2^{b} \,|{\mathcal G}(V\setminus\{x,y\},V_2,k)| \\ &\leq& 2^{\binom{n-2}{2}} \,n(n-1) \sum_{a=0}^{n-2}\tbinom{n-2}{a}\, 2^{(n-2-a)/2}\\ &=& 2^{\binom{n}{2}} \frac{1}{2}\,n(n-1) \biggl(\frac{1+ \sqrt{2}}{4}\biggr)^{n-2}. \end{eqnarray*} \end{proof} \renewcommand{\proofname}{Proof of Theorem {\rm\ref{newtheorem10}}} \begin{proof} By Corollary \ref{newc10} and Lemma \ref{l7l}, ${\mathcal H}_{\!n,3,\Delta}$ is a class of typical graphs of diameter $3$, each of which is Hamiltonian. From Lemma \ref{newlemma400} and the definition of the number $\xi_{n,3}$, as $n$ tends to infinity, we obtain \begin{equation}\label{new22} \frac{|{\mathcal FC}_{n,3}|}{2^{\binom{n}{2}} \xi_{n,3}}\leq 2\biggl(\frac{1+ \sqrt{2}}{3}\biggr)^{n-2}=o(1). \end{equation} Now, using Corollary \ref{newc10} and relation \eqref{new22}, we conclude $$2^{\binom{n}{2}}\xi_{n,3}(1-o(1))\leq |{\mathcal H}_{\!n,3,\Delta}\setminus {\mathcal FC}_{n,3}|\leq |{\mathcal J}_{n,\,d=3}|\leq 2^{\binom{n}{2}}\xi_{n,3}.$$ Hence, ${\mathcal H}_{\!n,3,\Delta}\setminus {\mathcal FC}_{n,3}$ is a typical class of graphs of diameter $3$, each of which does not satisfy Fan's condition. \end{proof} \renewcommand{\proofname}{Proof} As for FC(G), an analogous effect also occurs for Asratian's Condition AC(G). In \cite{asr}, A.S.~Asratian gave examples of such Hamiltonian graphs of any prescribed diameter. However, among graphs of diameter $3$, the class of graphs satisfying AC(G) is only asymptotically small. \begin{theorem}\label{newtheorem50} Almost all $n$-vertex graphs $G$ of diameter $3$ are Hamiltonian and do not satisfy {\rm AC(G)}. \end{theorem} \begin{proof} Consider the class ${\mathcal AC}_{n,3}$ of all $n$-vertex graphs of diameter $3$ with a unique pair of diametral vertices and satisfying AC(G). Let $F\in {\mathcal AC}_{n,3}$, and let $x$, $y$ be diametral vertices of the graph $F$. By uniqueness of the pair of diametral vertices, $B_2^F(v)=V(F)$ for every vertex $v\in V(F)\setminus \{x,y\}$. As in Lemma \ref{newlemma400}, we assume that $\deg_F x \leq (n-2)/2$ and consider the stratification of the graph $F$ by distance from the vertex $x$. Let $u\in V_2$. Then there is a shortest path $x,v,u$ of length 2, where $v\in V_1$. By AC(G), we obtain $\deg_F u \geq |B_2^F(v)|-1- \deg_F x \geq n-1-\deg_F x \geq n/2$ for every vertex $u\in V_2$. Thus, all properties of the graph $F$ used in Lemma \ref{newlemma400} hold. The following estimate is then established analogously. \begin{lemma} $|{\mathcal AC}_{n,3}|\leq 2^{\binom{n}{2}} \frac{1}{2}\,n(n-1) \Bigl(\frac{1+ \sqrt{2}}{4}\Bigr)^{n-2}.$ \end{lemma} \noindent As in Lemma \ref{newlemma400}, it follows that ${\mathcal H}_{\!n,3,\Delta}\setminus {\mathcal AC}_{n,3}$ is a typical class of graphs of diameter $3$; moreover, all graphs of this class are Hamiltonian by Lemma \ref{l7l} and do not satisfy {\rm AC(G)}. \end{proof} \begin{remark} The estimate obtained in the proof of Theorem {\rm\ref{newtheorem50}} for the number of graphs in the class ${\mathcal AC}_{n,3}$ can be substantially strengthened. However, it is sufficient for justifying the asymptotic smallness of this class. \end{remark} Among sufficient conditions for Hamiltonicity, the condition FGJLC(G), proposed by R.J.~Faudree, R.J.~Gould, M.S.~Jacobson, and L.M.~Lesniak \cite{fgjl}, is remarkable. As it turns out, this condition captures almost all graphs of diameter $3$. To prove this assertion, we shall use the class ${\mathcal H^*}_{\!n,3,\Delta}$ of $n$-vertex graphs of diameter $3$ constructed in Section 3, where a number of their properties were proved. \begin{theorem}\label{newtheorem40} Almost all $n$-vertex graphs $G$ of diameter $3$ are Hamiltonian and satisfy {\rm FGJLC(G)}. \end{theorem} \begin{proof} By Corollary \ref{s1b}, ${\mathcal H^*}_{\!n,3,\Delta}$ is a class of typical graphs of diameter $3$ for every $\Delta$, $0<\Delta < 1$. Let $3/4\leq\Delta < 1$, let $G\in {\mathcal H^*}_{\!n,3,\Delta}$, let $x,y$ be a pair of diametral vertices of the graph $G$, $z\in\{x,y\}$, and let $u,v\in V(G)\setminus \{x,y\}$. Using the property of intersections and differences of spheres of graphs in the class ${\mathcal H^*}_{\!n,3,\Delta}$, we obtain the required estimates \begin{align*} |S_1^G(x)\cup S_1^G(y)|\geq |S_1^G(x)|+|S_1^G(y)|\geq \frac{2n}{3}\,\Delta\geq \frac{n}{2}; \end{align*} \begin{align*} |S_1^G(z)\cup S_1^G(u)| &\geq |S_1^G(z)\setminus S_1^G(u)|+ |S_1^G(z)\cap S_1^G(u)|+|S_1^G(u) \setminus S_1^G(z)|\\ &\geq \frac{n}{6}\,\Delta + \frac{n}{6}\,\Delta + \frac{n}{3}\,\Delta\geq \frac{n}{2}; \end{align*} \begin{align*} |S_1^G(u)\cup S_1^G(v)| &\geq |S_1^G(u)\setminus S_1^G(v)|+|S_1^G(u)\cap S_1^G(v)|+ |S_1^G(v)\setminus S_1^G(u)|\\ &\geq \frac{3n}{4}\,\Delta\geq \frac{n}{2}. \end{align*} \end{proof} We now show that there exist sufficiently many rich, namely exponentially large, classes of $n$-vertex graphs of diameter $3$, each of which does not satisfy FGJLC(G) and at the same time is a $U$-graph. Indeed, let $\varepsilon$ be independent of $n$, and let $0<\varepsilon <1$. For every $\varepsilon$ and all sufficiently large $n$, consider the class of $n$-vertex graphs ${\mathcal K}_{n, 3, \varepsilon}$ consisting of all graphs of the form $G_3(H_1,F_1,F_3,F_2,H_2;a,b)$, defined as follows. Let $H_1$, $F_1$, $F_2$, $F_3$, $H_2$ be, respectively, an $h$-vertex, an $f_1$-vertex, an $f_2$-vertex, an $f_3$-vertex, and an $h$-vertex graph with pairwise disjoint vertex sets. Moreover, $H_1=\overline{K}_{h}$, $H_2=\overline{K}_{h}$, $F_1=K_{f_1-2}\cup {\overline K}_2$, $F_3=K_{f_3}$, $$h={\lfloor n\varepsilon/20\rfloor},$$ $$f_1={\lfloor n/2\rfloor}-1, \,f_2={\lfloor n/4\rfloor},\, f_3=n-2h - f_1 - f_2$$ and $a$, $b$ are isolated vertices of the graph $F_1$. We assume that $n$ is so large that the following inequalities hold \begin{equation}\label{888n} h\geq 2,\,\, f_1>f_2>2h,\,\,h+2f_2\geq f_1,\,\, 2f_3>h+f_2. \end{equation} \noindent Join vertices $u$ and $v$ by an edge in each of the following cases: $u\in V(H_1)$ and $v\in V(F_1)$; $u\in V(H_2)$ and $v\in V(F_2)$; $u\in V(F_i)$, $v\in V(F_j)$, and $i\neq j$. The resulting graph is denoted by $G_3(H_1, F_1,F_3,F_2,H_2;a,b)$. \begin{example} An example of a graph from the class ${\mathcal K}_{n,3,\varepsilon}$. \end{example} \noindent In Fig.\ref{fig551}, a graph $G_3(H_1,F_1,F_3,F_2,H_2;a,b)$ from the class ${\mathcal K}_{44,3,0.99}$ is shown for $n=44$ and $\varepsilon=0.99$. In this case, $H_1=\overline{K}_2$, $H_2=\overline{K}_2$, $F_1=K_{19}\cup {\overline K}_2$, $F_3=K_{8}$, and $f_2=11$. As the graph $F_2$, one may choose any $11$-vertex graph. The graph is shown schematically (only part of the edges between neighboring blocks is drawn). The Hamiltonian cycle of the graph $G_3(H_1,F_1,F_3,F_2,H_2;a,b)$ is highlighted in red. \begin{figure}[h] \centering \vspace{-1.5mm} \includegraphics[width=\textwidth]{1-2026} \vspace{-1.7mm} \caption{$G_3(H_1,F_1,F_3,F_2,H_2;a,b)\in {\mathcal K}_{44,3,0.99}$}\label{fig551} \end{figure} \begin{theorem}\label{700t} Every graph $G$ from the class ${\mathcal K}_{n,3, \varepsilon}$ is a $U$-graph of diameter $3$ and does not satisfy {\rm FGJLC(G)}. Moreover, for every such graph, {\rm FGJLC(G)} is violated both on a pair of vertices from $U$ and on a pair of vertices from $V(G)\setminus U$. The number of such graphs $|{\mathcal K}_{n,3, \varepsilon}|$ is $2^{\,\Theta(n^2)}.$ \end{theorem} \begin{proof} Let $G=G_3(H_1, F_1,F_3,F_2,H_2;a,b)$. Put $U=V(H_1)\cup V(H_2)$. Obviously, $G$ is a connected $n$-vertex graph of diameter $3$, and for every pair of diametral vertices $u$, $v$, we have $u\in H_i$ and $v\in H_j$, $i\neq j$. It is also easy to see that if $S$ is an independent set of the graph $G$ of maximum cardinality, then one of the following inclusions holds: $S\subseteq V(H_1)\,\cup\, V(F_2)$, $S\subseteq V(H_2)\cup \{a,b,c\}$, or $S=V(H_1)\cup V(H_2) \cup \{w\},$ where $w\in V(F_3)$ and $c\in V(F_1)\setminus \{a,b\}$. Hence, taking \eqref{888n} into account, we have \begin{equation}\label{29n} 2h + 1 \leq\alpha (G)\leq |V(F_2)|+|V(H_1)|=f_2 + h. \end{equation} Next, we have $|V(H_1)|\geq 2$ and $|S_1^G(u) \cup S_1^G(v)|=|V(F_1)|=f_1 < n/2$ if $u,v\in H_1$ and $u\neq v$. Hence, FGJLC(G) fails for any distinct vertices from $V(H_1)\subset U$. We now show that this condition also fails for the pair of vertices $a,b$. Indeed, we have $S_1^G(a)=S_1^G(b)=V(H_1)\cup V(F_2)\cup V(F_3).$ Hence, $$|S_1^G(a)\cup S_1^G(b)|=h+f_2+f_3=n-h-f_1<\frac n2,$$ since $f_1=\lfloor n/2\rfloor-1$ and $h\geq 2$. Thus, FGJLC(G) is also violated on a pair of vertices from $V(G)\setminus U$. We verify the properties of a $U$-graph. Let $u\in V(H_i)$, $i=1,2$. Taking \eqref{888n} into account, we obtain $$|S_1^G(u)|=|V(F_i)|>2|V(H_i)|=2h=|U|.$$ Hence, property (ii) in the definition of a $U$-graph holds. We now verify property (i). Let $u\in V(F_i)$ and $v\in V(F_j)$. First assume that $i=j$. It is easy to see that $V(F_1) \cup V(F_2)\cup (V(F_3)\setminus \{u,v\})\subseteq S_1^G(u)\cap S_1^G(v)$ for $i=3$, whereas for $i\neq 3$, we have $V(H_i)\cup V(F_s)\cup V(F_3) \subseteq S_1^G(u)\cap S_1^G(v)$, where $s\neq i$ and $s\neq 3$. Therefore, taking \eqref{888n} and \eqref{29n} into account, we obtain \begin{align*} |S_1^G(u) \cup S_1^G(v)|+ 2 |S_1^G(u) &\cap S_1^G(v)| \geq\\ &\geq3 |S_1^G(u) \cap S_1^G(v)| \\ &\geq 3(h+f_2+f_3)\\ &\geq 2h + f_1 +f_2+3f_3\\ &> n+h+f_2\\ &\geq n+ \alpha(G). \end{align*} Now let $\{i,j\}=\{1,2\}$. Obviously, $V(F_3)\subseteq S_1^G(u)\cap S_1^G(v)$ and $S_1^G(u)\cup S_1^G(v)=V(G)$. Therefore, taking \eqref{888n} and \eqref{29n} into account, we obtain \begin{eqnarray*} |S_1^G(u) \cup S_1^G(v)|+ 2 |S_1^G(u) \cap S_1^G(v)| &\geq& n+2f_3\\ &>& n+h+f_2\\ &\geq& n+\alpha(G). \end{eqnarray*} It remains to consider the case $i=3$ and $j\neq 3$. It is easy to see that $V(F_3)\setminus \{u\}\cup V(F_s)\subseteq S_1^G(u)\cap S_1^G(v)$ (here $s\neq i$ and $s\neq j$), and $V(F_1)\cup V(F_2)\cup V(F_3) \cup V(H_j)\subseteq S_1^G(u)\cup S_1^G(v)$. Therefore, taking \eqref{888n} and \eqref{29n} into account, we obtain \begin{eqnarray*} |S_1^G(u) \cup S_1^G(v)|+ 2 |S_1^G(u) \cap S_1^G(v)| &\geq& f_1+f_2+f_3+h+2(f_2+f_3-1)\\ &>& f_1+f_2+f_3+3h+f_2\\ &\geq& n+ \alpha(G). \end{eqnarray*} Hence, the required property (i) holds. Thus, $G$ is a $U$-graph. We estimate $|{\mathcal K}_{n,3,\varepsilon}|$. Note that $$G_3(H_1, F_1,F_3,F_2,H_2;b,a)=G_3(H_1, F_1,F_3,F_2,H_2;a,b).$$ Now, taking into account the above-mentioned property of diametral pairs and the definition of the graph $G_3(H_1, F_1,F_3,F_2,H_2;a,b)$, we obtain $$ |{\mathcal K}_{n,3, \varepsilon}|= \binom{n}{h}\binom{n-h}{h}\binom{n-2h}{f_1}\binom{n-2h-f_1}{f_2}\binom{f_1}{2}\,2^{\binom{\lfloor n/4\rfloor}{2}}= 2^{\,\Theta(n^2)}. $$ \end{proof} Note that for $n\geq 40/ \varepsilon$, all inequalities in \eqref{888n} hold. \begin{remark} The class ${\mathcal K}_{n,3, \varepsilon}$ is defined for every $n\geq 40/\varepsilon$. \end{remark} \noindent Theorem \ref{700t} shows that the difference between the $U$-condition and FGJLC(G) is not limited to individual exceptional graph examples. The constructed classes have exponential cardinality. Moreover, in the graphs of these classes, the FGJLC(G) condition is violated both on pairs of vertices from the distinguished set $U$ and on pairs of vertices outside $U$. This demonstrates that $U$-graphs provide not only an asymptotic explanation for typical Hamiltonicity but also a more flexible structural condition. \begin{remark} In the second part, we construct exponentially larger classes of $n$-vertex $U$-graphs of diameter $4$ that also fail to satisfy {\rm FGJLC(G)}. \end{remark} \section{Conclusion} Note that condition (i) in the definition of a $U$-graph is not a direct analogue of classical Ore-type conditions on vertex degrees, their generalizations, and the like. It relates the size of the union of neighborhoods of two vertices, the size of their intersection, and the local independence number $\alpha_G(u,v)$, calculated outside the balls of the graph $B_1^G(u)\cup B_1^G(v)$. Likewise, condition (ii) is not traditional; it identifies a distinguished set $U$ of vertices that prevents the application of "uniform"\/ Hamiltonian conditions. This form of the condition allows us to remove frequently encountered obstacles to determining Hamiltonianity and constructing a Hamiltonian cycle for $n$-vertex graphs of exponentially large classes. These results reveal several aspects of the new sufficient condition. On the one hand, the $U$-graph condition reveals a unified mechanism for proving the Hamiltonian property of almost all $n$-vertex graphs of diameter $k=1,2,3$. Thus, the well-known result on the typical Hamiltonicity of graphs of small diameter follows from a single general sufficient condition. On the other hand, the $U$-condition turns out to be significantly more flexible than the well-known "uniform"\/ Ore-type conditions, such as FGJLC(G). Although almost all graphs of diameter $3$ satisfy FGJLC(G), the exponential classes of $U$-graphs of diameter $3$ constructed in the paper show that the FGJLC(G) condition can be violated locally and does not cover many sufficiently rich Hamiltonian structures. Moreover, violation of FGJLC(G) can occur for both pairs of vertices in $U$ and for pairs of vertices outside $U$. Thus, the introduced sufficient condition turns out to be more sensitive to the internal structure of the graph for Hamiltonianity, which confirms its wide classical applicability outside the framework of the axiomatic approach. \bigskip \begin{thebibliography}{24} \bibitem{asr} A.S.~Asratian, \href{https://doi.org/10.1007/s00373-006-0646-3}{\it New Local Conditions for a Graph to be Hamiltonian}, Graphs and Combinatorics {\bf 22}(2), 2006, pp.153--160. \bibitem{dirac} G.A.~Dirac, \href{https://doi.org/10.1112/plms/s3-2.1.69}{\it Some theorems on abstract graphs}, Proc. London Math. Soc. {\bf(3)} 2 (1952), pp. 69--81. \bibitem{emel90} V.A.~Emelichev, O.I.~Melnikov, V.I.~Sarvanov, and R.I.~Tyshkevich, \href{https://zbmath.org/?q=an:0865.05001}{\it Lectures on Graph Theory}, B.I.Wissenschaftsverlag, Mannheim, 1994. \bibitem{fan} Geng-Hua~Fan, \href{https://doi.org/10.1016/0095-8956(84)90054-6}{\it New Sufficient Conditions for Cycles in Graphs}, Journal of Combinatorial Theory, Series B {\bf 37} (1984), pp. 221--227. \bibitem{fgjl} R.J.~Faudree, R.J.~Gould, M.S.~Jacobson, L.M.~Lesniak, \href{https://doi.org/10.1016/0012-365X(92)90132-Y}{\it Neighborhood unions and a generalization of Dirac's theorem}, Discrete Mathematics, {\bf 105}(1992), pp. 61--71. \bibitem{fti95} T.I.~Fedoryaeva, \href{https://doi.org/10.1007/978-94-011-5678-3\_5}{\it Operations and isometric embeddings of graphs related to the metric prolongation property}, Oper. Research and Discrete Anal., {\bf 2}:3 (1997), 31--49, translated from Diskretn. Anal. Issled. Oper., {\bf 2}:3 (1995), 49--67. \bibitem{fti15} T.I.~Fedoryaeva, \href{https://doi.org/10.17377/daio.2015.22.512}{\it The diversity vector of balls of a typical graph of small diameter}, Diskretn. Anal. Issled. Oper., {\bf 22}:6 (2015), 43--54. \bibitem{fti16} T.I.~Fedoryaeva, \href{https://doi.org/10.17377/semi.2016.13.033}{\it Structure of the diversity vector of balls of a typical graph with given diameter}, Siber. Electr. Math. Reports, {\bf 13} (2016), 375--387. \bibitem{fti17} T.I.~Fedoryaeva, \href{https://doi.org/10.1134/S1990478917020065}{\it Asymptotic approximation for the number of $n$-vertex graphs of given diameter}, J.Appl.Ind.Math., {\bf 11}:2 (2017), 204--214, translated from Diskretn. Anal. Issled. Oper., {\bf 24}:2 (2017), 68--86. \bibitem{fti22} T.I.~Fedoryaeva, \href{https://doi.org/10.33048/semi.2022.19.062}{\it Logarithmic asymptotics of the number of central vertices of almost all $n$-vertex graphs of diameter $k$}, Siber. Electr. Math. Reports, {\bf 19:2} (2022), 747--761. \bibitem{fti24} T.I.~Fedoryaeva, \href{https://doi.org/10.33048/semi.2024.21.098}{\it Are almost all $n$-vertex graphs of given diameter Hamiltonian?}, Siber. Electr. Math. Reports, {\bf 21:2} (2024), 1549--1561. \bibitem{fti26-2} T.I.~Fedoryaeva, {\it On $n$-vertex Hamiltonian graphs.{\rm~II~(}Ore-type Conditions and $U$-graphs{\rm)}}, Siber. Electr. Math. Reports, (2026), to appear. \bibitem{galvin} D.~Galvin, \href{https://doi.org/10.48550/arXiv.1406.7872}{\it Three tutorial lectures on entropy and counting}, arXiv:1406.7872, (2014). \bibitem{gould} R.J.~Gould, \href{https://zbmath.org/?q=an:0746.05039}{\it Updating the Hamiltonian Problem --- A Survey}, J. Graph Theory, {\bf 15:2} (1991), 121--157. \bibitem{grah94} Ronald~L.~Graham, Donald~E.~Knuth, and Oren Patashnik, \href{https://zbmath.org/?q=an:0836.00001}{\it Concrete Mathematics}, Addison-Wesley, 1994. \bibitem{xar69} F.~Harary, \href{https://zbmath.org/?q=an:0182.57702}{\it Graph Theory}, Addison--Wesley, London, 1969. \bibitem{jung} H.A.~Jung, \href{https://doi.org/10.1016/S0167-5060(08)70503-X}{\it On maximal circuits in finite graphs}, Annals of Discrete Math. {\bf 3}(1978), pp. 129--144. \bibitem{ush} V.P.~Kozyrev, S.V.~Yushmanov, \href{https://zbmath.org/?q=an:0606.05057}{\it Graph Theory (algorithmic, algebraic, and metric problems)}, Itogi Nauki Tekh. Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern., {\bf 23}(1985), pp. 68--117; J. Soviet Math., {\bf 39:1} (1987), 2476--2508. \bibitem{Matula} D.W.~Matula, \href{https://zbmath.org/?q=an:0209.28101}{\it On the Complete Subgraphs of a Random Graph}, Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and Its Applications, 1970, pp. 356--369. \bibitem{Moon&Moser} J.W.~Moon, L.~Moser, \href{https://zbmath.org/?q=an:0142.27102}{\it Almost all {\rm (0,1)} matrices are primitive}, Stud. Sci. Math. Hung., {\bf 1} (1966), pp. 153--156. \bibitem{Moon} J.W.~Moon, \href{https://doi.org/10.4153/CMB-1972-008-3}{\it Almost all graphs have spanning cycle}, Canad. Math. Bull., 15 (1972), pp.39--41. \bibitem{nara} C.~Nara, \href{https://zbmath.org/?q=au:Nara%20ti:%22On%20sufficient%20conditions%20for%20a%20graph%20to%20be%20hamiltonian%22}{\it On sufficient conditions for a graph to be hamiltonian}, Natur. Sci. Rep. Ochanomizu Univ. {\bf 31}(1980), pp.75--80. \bibitem{ore} O.~Ore, \href{https://doi.org/10.2307/2308928}{\it Note on Hamilton circuits}, The American Mathematical Monthly {\bf 67:1}(1960), p. 55. \bibitem{perepel} V.A.~Perepelitsa, \href{https://zbmath.org/?q=an:0214.51702}{\it On two problems from the theory of graphs}, Sov. Math., Dokl.11 (1970), 1376--1379. Translation from Dokl. Akad. Nauk SSSR, 194:6 (1970), 1269--1271. \end{thebibliography} \end{hyphenrules} \end{document}