Graph

Definition

A graph, or simple graph, is a pair $G = (V, E)$ of a set $V$ and a set $E$ of $2$-element subsets of $V$. The elements of $V$ are the vertices of $G$, and the elements of $E$ are its edges. Two vertices $u$ and $v$ are adjacent if $\{u, v\} \in E$. The notation for this edge is $uv$, and the notation for adjacency is $u \sim v$.

Equivalently, a graph is a set $V$ with a relation $\sim$ on $V$ that is symmetric and irreflexive. A graph is finite if $V$ is finite.

Remarks

In a simple graph, no edge joins a vertex to itself, and two vertices are joined by at most one edge. A multigraph drops the second condition, and some variants allow loops. In a directed graph the edges are ordered pairs. The set $E$ is the edge set of $G$.

Explanations

L1 human

A graph is a set of points with lines between some pairs of points. For example, the people at a party are vertices, and two people are joined by an edge when they know each other.