Eulerian Paths, Hamiltonian Cycles & Kuratowski Planarity

1. Eulerian Graph (Edge Traversal):

- Eulerian Path: A trail visiting every edge exactly once.

- Eulerian Circuit: A closed trail visiting every edge exactly once.

Theorem: A connected graph has an Eulerian circuit iff every vertex has even degree. It has an Eulerian path iff exactly 0 or 2 vertices have odd degree.

2. Hamiltonian Graph (Vertex Traversal):

- Hamiltonian Cycle: A closed cycle visiting every vertex exactly once.

- Determining whether a general graph is Hamiltonian is NP-Complete.

- Dirac's Theorem: If G is a simple graph with n >= 3 vertices and deg(v) >= n / 2 for all v, then G is Hamiltonian.

- Ore's Theorem: If deg(u) + deg(v) >= n for every pair of non-adjacent vertices u, v, then G is Hamiltonian.

A graph is Planar if it can be embedded in a 2D plane such that no edges intersect except at vertices.

Euler's Planar Formula:

V - E + F = 2 (where F is the number of regions/faces, including the outer unbounded region).

Boundary Invariant:

Each face is bounded by at least 3 edges. In planar graph G, 2E = sum_{f} text{deg}(f) >= 3F implies F <= frac{2E}{3}.

Substituting into Euler's formula:

2 = V - E + F <= V - E + frac{2E}{3} = V - frac{E}{3}

frac{E}{3} <= V - 2 implies E <= 3V - 6.

If G contains no triangles (each face has degree >= 4, as in bipartite graphs):

2E >= 4F implies F <= frac{E}{2} implies E <= 2V - 4.

Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph homeomorphic to K_5 (complete graph on 5 vertices) or K_{3,3} (utility bipartite graph).