Graph Theory Basics

Basic Terminology

• Degree of a vertex in an undirected graph counts the number of edges incident to it; loops at the vertex contribute twice to the degree.
• Denoted as deg(v) for a vertex v.

Vertex Degree Examples

• In a graph with vertices P, Q, R, and S:
  • deg(P) = 2
  • deg(Q) = 3
  • deg(R) = 2
  • deg(S) = 1

Adjacent Vertices

• Two vertices u and v are adjacent if they share an edge e.
• An edge e connects u and v; u is the initial vertex and v is the terminal vertex.
• For loops, the initial and terminal vertices are the same.

Directed Graphs

• In directed graphs, if there is an edge (u, v), then u is adjacent to v and v is adjacent from u.

Edge Multiplicity

• If m different edges connect the same unordered pair of vertices {u, v}, it's referred to as an edge of multiplicity m.

Self-Connecting Edges

• Loops represent edges connecting a vertex to itself, important for modeling networks, e.g. communications links.

Directed Graph Characteristics

• Directed graphs consist of vertices and directed edges (arcs) with arrows indicating the direction.
• Can contain loops, multiple edges, and bidirectional edges.

Simple Directed Graph

• A simple directed graph has no loops or multiple edges; at most one edge exists between any two vertices.
• An edge of multiplicity m is considered if m directed edges exist between vertices (u, v).

In-Degree and Out-Degree

• In a directed graph, in-degree (deg⁻(v)) counts edges leading to vertex v, while out-degree (deg⁺(v)) counts edges originating from vertex v.
• Loops contribute 1 to both in-degree and out-degree of the vertex.

Degree Sequence

• The degree sequence arranges vertex degrees in non-increasing order.
• In directed graphs, both in-degrees and out-degrees are considered.

Example of Degree Sequence

• For the graph G with vertices {A, B, C, D} and edges {(A, B), (A, C), (B, C), (C, D)}:
  • Degree sequence in non-increasing order: {3, 2, 2, 1}
  • Minimum degree is the smallest degree of any vertex; maximum degree is the largest.

Theorems

• For directed graphs, the total degree sum equals the number of directed edges:
  • ∑ deg(v) = |E|
• Handshaking Theorem for undirected graphs states the sum of all vertex degrees equals twice the number of edges:
  • ∑ deg(v) = 2m, applicable even with multiple edges and loops.