Graph Basics

What Is a Graph?

A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices. Graphs model relationships between objects.

Vertex (Node): A fundamental unit of a graph
Edge:          A connection between two vertices
Degree:        The number of edges incident to a vertex
Neighbor:      Two vertices connected by an edge
Path:          A sequence of edges connecting two vertices
Cycle:         A path that starts and ends at the same vertex

Basic Terminology

Adjacent: Two vertices connected by an edge
Incident: An edge is incident to its endpoints
Loop:     An edge connecting a vertex to itself
Parallel: Multiple edges between the same two vertices
Isolated: A vertex with degree 0

Handshaking Lemma:
  The sum of degrees of all vertices = 2 × |E|
  (Each edge contributes 2 to the total degree)

Representing Graphs

1. Adjacency Matrix:
   A[i][j] = 1 if edge exists between i and j, 0 otherwise

   For undirected graphs: A is symmetric

2. Adjacency List:
   Each vertex stores a list of its neighbors
   More memory-efficient for sparse graphs

3. Edge List:
   Simply list all edges as pairs