Discover published sets by community

Ore's Theorem is a criterion for the existence of a Hamiltonian Circuit in a graph. It states that if a graph has $n \geq 3$ vertices, and for every pair of non-adjacent vertices $u$ and $v$, the sum of their degrees is at least $n$, then the graph has a Hamiltonian Circuit.

An Eulerian Path is a path that uses each edge of a graph exactly once. Existence conditions: For a connected graph, if exactly 0 or 2 vertices have odd degree, an Eulerian Path exists.

A Hamiltonian Circuit is a Hamiltonian Path that starts and ends at the same vertex, forming a cycle. Existence conditions: No easy necessary and sufficient conditions exist, but a graph needs to be sufficiently connected to have a Hamiltonian Circuit.

An Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex, thus forming a cycle. Existence conditions: For a connected graph, an Eulerian Circuit exists if and only if all vertices have even degree.

Euler's Theorem states that a connected graph possesses an Eulerian Circuit if and only if every vertex has an even degree.

A Hamiltonian Path is a path that visits each vertex of a graph exactly once. Existence conditions: No easy necessary and sufficient conditions, but Dirac's and Ore's theorems give sufficient conditions for Hamiltonian Paths in certain graphs.

Dirac's Theorem provides a condition for the existence of a Hamiltonian Circuit in a graph. It states that if a graph has $n \geq 3$ vertices, and every vertex has degree at least $\frac{n}{2}$, then the graph has a Hamiltonian Circuit.

A Semi-Eulerian Graph has an Eulerian Path but not an Eulerian Circuit. Existence conditions: The graph is connected and exactly two vertices have an odd degree.

A Semi-Hamiltonian Graph has a Hamiltonian Path but not a Hamiltonian Circuit. Existence conditions: Sufficient conditions are similar to Hamiltonian Graphs but less restrictive, often related to graph connectivity and degree sequences.