What Are the Core Concepts of Graph Theory? A Beginner’s Guide

1 Basic Concepts of Graphs

A graph \(G = (V, E)\) consists of a non‑empty finite set \(V\) of vertices and a set \(E\) of edges, where each edge connects vertices in \(V\). The notation \(|V|\) denotes the number of vertices and \(|E|\) denotes the number of edges.

2 Undirected and Directed Graphs

If the edges have no direction, the graph is called an undirected graph (often simply “graph”). An edge without direction is an undirected edge . An edge connecting vertices \(u\) and \(v\) is denoted by \(\{u,v\}\) or \((u,v)\).

If the edges have a direction (arrows), the graph is called a directed graph . Its edges are called arcs (or directed edges). An arc from vertex \(u\) to vertex \(v\) is denoted by \((u, v)\), where \(u\) is the tail (origin) and \(v\) is the head (destination). A directed graph is usually written as \(G = (V, A)\), where \(V\) is the vertex set and \(A\) is the arc set.

3 Simple Graphs and Complete Graphs

Definition 1 : For an edge \(e\) of a graph, its two endpoints are called the adjacent vertices of \(e\); the edge is said to be incident to those vertices. Two edges sharing a common endpoint are called adjacent edges . Multiple edges between the same pair of vertices are parallel edges . An edge whose two endpoints coincide is a loop . A vertex not incident to any edge is an isolated vertex .

Definition 2 : A graph without loops and without parallel edges is called a simple graph .

Definition 3 : A simple graph in which every pair of distinct vertices is adjacent is a complete graph . The complete graph with \(n\) vertices is denoted by \(K_n\).

4 Weighted Graphs

Definition 4 : If each edge of a graph is assigned a real number weight, the graph is called a weighted graph (or network). The weight of an edge \(e\) is denoted by \(w(e)\). Weights can represent distance, cost, time, benefit, etc.

If a directed graph has a weight assigned to each arc, it is called a directed weighted graph .

5 Vertex Degree

Definition 5 :

(1) In an undirected graph, the number of edges incident to a vertex \(v\) (counting loops twice) is the degree of \(v\), denoted \(deg(v)\).

(2) In a directed graph, the number of arcs leaving \(v\) is the out‑degree , denoted \(outdeg(v)\); the number of arcs entering \(v\) is the in‑degree , denoted \(indeg(v)\). The sum \(outdeg(v)+indeg(v)\) is the (total) degree of \(v\).

Vertices with odd degree are called odd vertices ; those with even degree are called even vertices .

Theorem 1 : For any graph \(G\), the sum of the degrees of all vertices equals twice the number of edges, i.e., \(\sum_{v\in V}deg(v)=2|E|\).

Corollary 1 : In any graph, the number of odd‑degree vertices is even.

6 Subgraphs

Definition 6 : Let \(G\) and \(H\) be two graphs. If \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\), then \(H\) is a subgraph of \(G\). If \(V(H)=V(G)\), \(H\) is a spanning subgraph of \(G\).

7 Paths and Circuits

A sequence of edges connecting vertices \(v_0, v_1, \dots, v_k\) is called a road (or walk). If all edges are distinct, the road is a trail . If all vertices are distinct, it is a path . A path whose start and end vertices coincide is a cycle (or circuit). The length of the shortest path between two vertices defines the distance between them.

8 Connected and Disconnected Graphs

In an undirected graph, if there exists a road between vertices \(u\) and \(v\), they are said to be connected . If every pair of vertices in the graph is connected, the graph is a connected graph ; otherwise it is a disconnected graph . Each maximal connected subgraph of a disconnected graph is a connected component .

In a directed graph, if for any two vertices \(u\) and \(v\) there are directed roads from \(u\) to \(v\) and from \(v\) to \(u\), the graph is strongly connected .

References

Python数学实验与建模 / 司守奎, 孙玺菁, 科学出版社