Essential Graph Theory Formulas and Concepts

Handshaking Lemma

In any undirected graph, the sum of the degrees of all vertices is twice the number of edges.

Formula: Σdeg(v) = 2|E|

Euler's Formula for Planar Graphs

For planar graphs, the relationship between vertices (V), edges (E), and regions (R) is defined as:

V - E + R = 2

Sum of Degrees and Odd Vertices

The sum of the degrees of all vertices in any graph is always even because each edge contributes 2 to the total sum. Furthermore, the number of vertices with an odd degree must always be even.

Graphs with No Odd Degree Vertices

If all vertices in a graph have an even degree, the graph is Eulerian, meaning it contains an Eulerian circuit.

Complete Graphs

A complete graph with n vertices, denoted as K_n, has an edge between every pair of distinct vertices. The number of edges is calculated as:

Number of edges = n(n - 1) / 2

Simple Circuits

A simple circuit (or simple cycle) is a path that starts and ends at the same vertex and does not repeat any vertices (except for the starting/ending vertex).

Finding Vertices of Specific Degrees

When a graph has vertices of only two different degrees (d₁ and d₂), use the following formula to find the number of vertices of a certain degree (where d₁ is the smaller degree):

#degree d₂ = [d₁(total vertices) - 2(total edges)] / (d₁ - d₂)

Connectivity and Cut Vertices

Removing a cut vertex from a connected graph will disconnect the graph or make it more fragmented. Edge connectivity (λ(H)) is the minimum number of edges you must remove to disconnect the graph.

Eulerian Circuits and Paths

• Eulerian Circuit: A closed loop that visits every edge exactly once and returns to the starting vertex. A graph has an Eulerian circuit if and only if it is connected and every vertex has an even degree.
• Eulerian Path: A path that visits every edge exactly once. A graph has an Eulerian path if and only if it is connected and has exactly 0 or 2 vertices with an odd degree.

Hamiltonian Paths and Cycles

A Hamiltonian path is a path that visits every vertex in the graph exactly once. If the path also returns to the starting vertex, it is called a Hamiltonian cycle (or circuit).

Example: A → B → C → D