A graph represents objects and pairwise connections between them.

An undirected graph can be written as

$$G=(V,E),$$

where $V$ is the set of vertices and $E$ is a set of edges joining pairs of vertices.

Adjacency and degree

Two vertices are adjacent when an edge joins them. The degree of a vertex is the number of incident edges.

In a finite undirected graph,

$$\sum_{v\in V}\deg(v)=2|E|.$$

Each edge contributes once to the degree of each endpoint. This is the handshaking lemma.

Graphs abstract away the physical meaning of the objects and keep only connectivity. The same structure can represent roads, social links, dependencies, circuits or states and transitions.