One criterion of existence of a Hamiltonian cycle (Q1387766): Difference between revisions

Let \(G=(X, A)\) be a finite connected graph. Further, let \(X_1\subset X\) be some independent set of vertices of the graph \(G.\) Denote by \(P(X_1)\) set of all paths connecting vertices of the set \(X_1.\) Call the set of vertices \(U(P(X_1))\subset X\) \((U(P(X_1))\cap X_1=\varnothing)\) separating for the vertices of the set \(X_1\), if removing these vertices from the graph \(G\) along with their incident edges cuts each path of \(P(X_1).\) A separating set \(\overline{U} (P(X_1))\) is called minimum if \(\text{Card}(\overline{U} (P(X_1)))\leq \text{Card} (U(P(X_1)))\), where \(U(P(X_1))\) is any separating set of vertices for the set \(X_1.\) The main result of this note is the following theorem: A finite graph \(G=(X, A)\) is Hamiltonian if and only if \(\text{Card} (X_1)\leq \text{Card} (\overline{U} (P(X_1)))\) for any independent set of vertices \(X_1\subset X\).