What is the difference between an Eulerian and a Hamiltonian cycle?

An Eulerian circuit uses every edge exactly once, while a Hamiltonian cycle visits every vertex exactly once; the former has a simple degree characterization, but deciding the latter is computationally hard.

What does it mean for a graph to be k-connected?

A graph is k-connected if it remains connected whenever fewer than k vertices are removed, quantifying its resilience to vertex failures.

Graph Fundamentals and Connectivity

The fundamentals of graph theory introduce graphs, their basic parameters, and the notions of connectivity and traversal that describe how a graph holds together.

Definition

A graph consists of a set of vertices and a set of edges joining pairs of vertices; connectivity measures the extent to which the graph remains in one piece when vertices or edges are removed.

Scope

This topic covers the definitions of graphs and digraphs, degree and the handshaking lemma, subgraphs and isomorphism, walks, paths and cycles, connectivity and components, and the classical characterizations of Eulerian and Hamiltonian graphs. It establishes the vocabulary and core structural results used throughout graph theory.

Core questions

What are the basic parameters - order, size, and degree - of a graph?
When is a graph connected, and how robust is its connectivity to deletion?
When does a graph admit a closed walk using every edge exactly once?
How do paths and cycles encode reachability and structure?

Key concepts

Vertices, edges, and degree
Walks, paths, and cycles
Connected components
Vertex and edge connectivity
Eulerian circuits
Hamiltonian cycles

Key theories

Handshaking lemma: In any graph the sum of all vertex degrees equals twice the number of edges, which immediately implies that the number of vertices of odd degree is even.
Euler's theorem on Eulerian circuits: A connected graph has a closed walk traversing every edge exactly once if and only if every vertex has even degree, the result underlying Euler's solution of the Konigsberg bridges.

Clinical relevance

Connectivity analysis is central to network reliability, routing, and the design of fault-tolerant communication and transport systems, while Eulerian and Hamiltonian structures arise in routing and sequencing problems.

History

Euler's 1736 Konigsberg paper introduced graph traversal; Menger's 1927 theorem gave the foundational duality between connectivity and disjoint paths that anchors the modern theory.

Key figures

Leonhard Euler
Karl Menger

Seminal works

diestel2017

Frequently asked questions

What is the difference between an Eulerian and a Hamiltonian cycle?: An Eulerian circuit uses every edge exactly once, while a Hamiltonian cycle visits every vertex exactly once; the former has a simple degree characterization, but deciding the latter is computationally hard.
What does it mean for a graph to be k-connected?: A graph is k-connected if it remains connected whenever fewer than k vertices are removed, quantifying its resilience to vertex failures.