Undirected Graphs

Why

We want to visualize symmetric relations.

Definition

An undirected graph (or graph, network) is a pair $(V, E)$ in which $V$ is a nonempty set and $E$ is a subset of the set of unordered pairs of elements in $V$. We call the elements of $V$ the vertices (or points) of the graph and the elements of $E$ the edges (or arcs, lines). We call $(V, E)$ an undirected graph on $V$.

Two vertices are adjacent (or neighboring) if the unordered pair containing them is in the edge set. We say that the corresponding edge is incident to those vertices. The adjacency set of a vertex is the set of vertices adjacent to it. The degree (or valency) of a vertex is the number of vertices adjacent to it; in other words, the size of its adjacency set. A graph is complete if every pair of two distinct vertices is adjacent.

The complement (or graph complement, or complementary graph) of $(V, E)$ is the graph $(V, F)$ where $F$ is the complement of $E$ in the set of pairs from $V$.

Other terminology

Some authors call the adjacency set the neighborhood of the vertex. They call the union of the adjacency set of the vertex $v \in V$ with the singleton $\set{v}$ the closed neighborhood of $v$.

When $\set{x,y} \in E$, some authors say that the edge “joins” the vertices, and call $x$ and $y$ the end vertices (or ends) of the edge.

Some authors call two edges adjacent if they have exactly one common end vertex.

Self-loops

Some authors include a concept of a self-loop, which is meant to be an edge from one node to itself. However, we do not allow this as the set $\set{u, u}$ is not a pair.

Notation

Let $V$ be a nonempty set. Let $E \subset \Set*{\set{v, w}}{v, w \in V}$. Then the pair $(V, E)$ is an undirected graph. We regularly say “Let $G = (V, E)$” be a graph, in which the relevant properties of $V$ and $E$ are implicit.

The notation $\set{v, w} \in E$ for an edge between vertices $v, w \in V$ reminds us that the edges are unordered pairs of distinct vertices. We denote the adjacency set of $v$ by $\adj(v)$ and the degree of $v$ by $\deg(v)$.

Some authors will denote the vertex set of a graph they are denoting by $G$ by $V(G)$ and the edges set by $E(G)$.

Example

Suppose $V = \set{a, b, c, d, e}$. Define

\[ E = \set*{\set{a, b}, \set{a, c}, \set{a, e}, \set{b, d}, \set{b, e}, \set{c, d}, \set{c, e}, \set{d,e}}. \]