Intereting Posts

Is Category Theory geometric?
Given an infinite poset of a certain cardinality, does it contains always a chain or antichain of the same cardinality?
Is greatest common divisor of two numbers really their smallest linear combination?
Prove that a holomorphic function injective in an annulus is injective in the whole ball
Construction of an exact sequence $1 \to N_{16} \to G_{64} \to \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \to 1$
Invariance of residues modulo $p$
$B$ is a Borel set, implies $f(B)$ is a Borel set.
Trigonometric and exp limit
Find the matrix of $\langle f, g \rangle = \displaystyle\int_0^1 f(t) g(t) \, \mathrm dt$ with respect to the basis $\{1,t,\dots,t^n\}$
Prove that the only eigenvalue of a nilpotent operator is 0?
Show that $\sum_{n=-\infty}^\infty (x+n\pi)^{-2} = \sin^{-2}(x) $
Homogeneous polynomial in $k$ can factor into linear polynomials?
A square of a rational between two positive real numbers ?!
What are the norms in Ito isometry?
Unique critical point does not imply global maximum/global minimum

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it’s indeterminable with minimal information:

```
A graph has 17 vertices and 129 edges.
```

Hamiltonian graphs are proved by, as long as the vertices are greater than or equal to 3 (which this is), then if the sum of the degrees of two non-adjacent vertices is greater than or equal to the vertices (17 in this case), the graph is Hamiltonian.

To me this looks like some type of pigeonhole principle proof. I need to determine if there can exist 2 non-adjacent vertices with degrees summing to 17 or greater.

- Different shapes made from particular number of squares
- chromatic number of a graph versus its complement
- On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in $, with diagonal moves allowed
- Number of solutions of $x_1+x_2+\dots+x_k=n$ with $x_i\le r$
- Asymptotics of binomial coefficients and the entropy function
- Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)

Could anyone help me figure out how to think about this?

I’ve gathered that each vertex must be at least of degree 1 (or else the graph would be disconnected), and that at least one vertex will have more than one degree due to the pigeonhole concept.

From there I’m unsure how to approach it.

Thanks for any help.

Edit:

Doesn’t Dirac’s theorem state that the vertices degree must ALL be greater than or equal to n/2, in this case, 8.5, or maybe 9?

I hadn’t considered that before, but that still leaves me with the same question, how can I prove (probably with pigeonhole) that each vertex will have at least 9?

- How many arrangements of MATHEMATICS are there in which each consonant is adjacent to a vowel?
- $m$ balls into $n$ urns
- Finding a combinatorial argument for an interesting identity: $\sum_k \binom nk \binom{m+k}n = \sum_i \binom ni \binom mi 2^i$
- A game with two dice
- Simplification of $\binom{50}{0}\binom{50}{1} + \binom{50}{1}\binom{50}{2}+⋯+\binom{50}{49}\binom{50}{50}$
- What do we call well-founded posets whose elements have a unique height?
- Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?
- Generate Random Latin Squares
- Counting Combinations of a List of Numbers
- Solutions to Binary Equations

Dirac’s theorem says that the graph is Hamiltonian if every vertex has degree at least $9$. So suppose there is a vertex $v$ with degree $8$ or less.

If the remaining $16$ vertices form a complete graph, they each have degree $15$, except for the extra $8$ vertices connected to $v$ that have degree $16$. That graph has the most edges possible while remaining non-Diracian. Then, the number of edges is half the sum of the degrees, or $\frac{1}{2} (8 + 15\cdot 8 + 16 \cdot 8) = 128$ edges.

To force a Hamiltonian cycle in an undirected graph on $n$ vertices would require at least $ {{n-1}\choose 2} + 2 $ edges, which is one more than the number of edges in a complete graph on $(n-1)$ vertices plus one edge connecting that graph to the $n$’th vertex.

For $n=17$ that is $122$, so unless there is a better construction of a very dense non-Hamiltonian graph, $129$ edges are more than enough. $129$ is the minimum number needed to force the applicability of Dirac’s theorem but that is a stronger requirement.

**Update.** There is no “better construction”. That $ {{n-1}\choose 2} + 1 $ is the maximum size of a non-Hamiltonian graph was proved by Ore (*Arc coverings of graphs*) in 1961 and uniqueness of the maximal graph was proved by Bondy (*Variations on the Hamiltonian theme*) in 1972. Therefore, $122$ edges are necessary and sufficient when $n=17$.

The graph is $7$ edges short from being complete so the minimum degree is $16 – 7 = 9$. Hence you can apply Dirac theorem.

- Factorial of a matrix: what could be the use of it?
- Some questions about the gamma function
- Is the figure the circumference of a unit circle?
- Fundamental group of two tori with a circle ($S^1✕${$x_0$}) identified
- If I roll three dice at the same time, how many ways the sides can sum up to $13$?
- Trigonometric Inequality. $\sin{1}+\sin{2}+\ldots+\sin{n} <2$ .
- Find polynomial $f(x)$ based on divisibility properties of $f(x)+1$ and $f(x) – 1$
- How do pocket calculators calculate exponents?
- Solving $\cos x=x$
- Cancellation of Direct Product in Grp
- Characterization of sets of differentiability
- order of operations division
- Verifying proof :an Ideal $P$ is prime Ideal if $R/P$ is an integral domain.
- Second longest prime diagonal in the Ulam spiral?
- Bergman-Shilov Boundary and Peak Points