Dirac’s Theorem says: If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian. Now I want to prove this theorem by induction on $n$. For $i=3$, we have $\delta(G) \ge 2$ which means our graph is complete. So, it has a cycle with the length of $n-1+1=n$ […]

By defining the following algorithm I was able to generate some interesting graphs using the values of the gaps between consecutive primes: Start in any prime $p_i$, this will be the initial node, and calculate the distance to the next prime, then define $d_1 = d(p_i,p_{i+1})$ The next node will be the prime $p_{i+d_1}$. Then […]

Given a bicubic planar graph consisting of faces with degree $4$ and $6$, so called Barnette graphs. We can show that there are exactly six squares. Kundor and I found six types of arrangements of the six squares: three pairs of squares $(2+2+2)$ two triples arranged in row $(\bar3+\bar3)$ two triples arranged like a triangle […]

Prove that every $8$-regular graph has $4$- and $2$-regular spanning subgraphs. Note: A graph is spanning subgraph, if it contains every vertex of the original graph. Furthermore this example’s from Hamiltonian cycle/path topic.

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 […]

I need to show that the maximum number of edges of non-Hamiltonian, simple graph, on $n$ vertices noted by $t(n,H_n)$ is $\binom{n-1}{2} + 1$. It’s essential to show the upper and lower bounds for this question. Now, I can see why I need to show the upper bound – for $t(n,H_n) > \binom{n-1}{2} + 1$ […]

How to prove “Prove $P_m X P_n$ (graph cartesian product) is Hamiltonian if and only if at least one of $m,n$ is even” Graph cartesian product is Grid graph, if I figure out $P_2 X P_2$ it will be $C_4$ (it is Hamiltonian). How to state this prove ?

I’m trying to find out if it is possible to construct a connected Hamiltonian and a connected non-Hamiltonian graph using the same degree sequence. For disconnected graphs it would be easier, I could choose a degree sequence of $(2,2,2,2,2,2)$ and have $C_6$, which has a Hamiltonian path, and two disjoint 3-cycles, which are non-Hamiltonian. How […]

It is generally difficult to determine whether a (large) graph have no Hamilton cycle (As opposed to determining whether it has any Euler circuit). This example illustrates a method (which sometimes work) to indicate that a graph has no Hamilton cycle. a. Show that if m and n are odd integers (not both = 1), […]

For any graph with order $n \geq 3$, given that its size is $$m \geq \frac{\left(n-1\right)(n-2)}{2} + 2,$$ show that the graph is Hamiltonian. I know that if I can show that the degree sum of any two non-adjacent vertices is $\geq n$, then I’d be done. Likewise, if I could show that the above […]

Intereting Posts

Conditions for vectors to span a vector space
A smooth function's domain of being non-analytic
“Direct” proof for a bound on the difference between endpoints of a path?
Integration using exponent
Computing an awful integral
How to Visualize points on a high dimensional (>3) Manifold?
Find the Average Velocity and the Instantaneous Velocity
If $\phi$ is a tautology then dual $\phi$ is a contradiction.
Uncountable chains
Questions on atoms of a measure
Solving an equation with floor function
Calculating $\iint (x+y) \, dx \, dy$
Entire function bounded by polynomial of degree 3/2 must be linear.
Can $\sin n$ get arbitrarily close to $1$ for $n\in\mathbb{N}?$
What is the sum of the first $p+q $ terms of this A.P.?