Essential Definitions and Theorems in Graph Theory

M1: Fundamental Graph Definitions

Walks, Paths, and Circuits

Walk

A Walk is a finite alternating sequence of vertices and edges, beginning and ending with vertices, such that each edge is incident with the vertices preceding and following it. No edge appears more than once in a walk, though a vertex may appear multiple times.

• Closed Walk: A walk that begins and ends at the same vertex.
• Open Walk: A walk that begins and ends at different vertices.

Path

A Path is an open walk in which no vertex appears more than once. The number of edges in a path is called the length of the path. A self-loop can be included in a walk but not in a path. The terminal vertices of a path are of degree 1, and the remaining intermediate vertices are of degree 2.

Circuit

A Circuit is a closed walk in which no vertex appears more than once, except for the initial and final vertex (which are the same).

Vertex and Graph Types

• Isolated Vertex: A vertex having no incident edge.
• Pendant Vertex: A vertex having degree 1.
• Null Graph: A graph whose edge set is empty.

Handshaking Theorem

The Handshaking Theorem states that the sum of the degrees of the vertices of a graph is twice the number of edges.

Proof of the Handshaking Theorem

Since the degree of a vertex is the number of edges incident with that vertex, the sum of degrees counts the total number of times an edge is incident with a vertex. Because every edge is incident with exactly two vertices, each edge gets counted twice—once at each end. Thus, the sum of the degrees is equal to twice the number of edges.

Isomorphism and Euler Graphs

Isomorphism

Two graphs $G$ and $G'$ are said to be isomorphic to each other if there is a one-to-one bijection between their vertices and edges such that the incidence relationship is preserved. Two isomorphic graphs must have the same number of edges, the same number of vertices, and the same degree sequence.

M2: Euler Graph

A connected graph $G$ is said to be an Euler Graph if there is a closed trail that includes every edge of the graph.

Applications of Graph Theory

Graph theory is applied in:

• Utilities Problem
• Seating Problem
• Electrical Network Problem

The Konigsberg Bridge Problem

The Konigsberg Problem asks: Starting from any of the four land areas (A, B, C, D), is it possible to cross each of the seven bridges exactly once and return to the starting point without swimming across the river?

In graph theory terms:

• Vertices represent the landmasses.
• Edges represent the bridges.

It was finally concluded that the desired walking tour of Konigsberg is not possible (as it requires an Euler circuit, which the resulting graph does not possess).

Graph Theory Proofs and Problems

Maximum Edges in a Simple Graph

Question: Prove that a simple graph with $n$ vertices and $k$ components can have at most $\frac{(n-k)(n-k+1)}{2}$ edges.

Part II