User:Scshunt/Definition:Graph

Informal Definition

A graph is intuitively defined as a pair consisting of a set of nodes or vertices and a set of edges.

In the above, the vertices (singular: vertex) are the points $A, B, C, D, E, F, G$ which are marked as dots. The edges are the links $AB, AE, BE, CD, CE, CF, DE, DF, FG$.

Formal Definition

There are three commonly-used formal definitions of a graph. Each makes it easier to express certain properties and formulations, so there is no. The definition here is the most easily generalized.

We define a graph to be an ordered triple $\left(V, E, \phi\right)$, where $V$ and $E$ are sets, and $\phi$ is a mapping $V \times E \to \left\{0, 1\right\}$ such that:

• Every edge is incident to exactly two vertices.
• No two edges are incident to the same two vertices.

We call $V$ and $E$ the vertex set and edge set, respectively. Their elements are called vertices (singular: vertex) and edges.

We call $\phi$ the incidence function, and we say that a vertex $v$ and an edge $e$ are incident if and only if $\phi(v, e) = 1$.

We say that two vertices are adjacent if and only if there is some edge incident to both of them.

Equivalent Definitions

There are two other commonly-used definitions of graphs. They are equivalent to the above definition. Because of the equivalence, we may use them interchangeably.

Edges as Sets

We can also define a graph as an ordered pair $\left(V, E\right)$ where:

• $V$ is a set, and
• $E$ is a set of two-element subsets of $V$.

In this case, $v \in V$ is incident to $e \in E$ if and only if $v \in e$, and $u, v \in V$ are adjacent if and only if $\left\{u, v\right\} \in E$.

Edges as Pair

We can also define a graph as an ordered pair $\left(V, E\right)$ where:

• $V$ is a set, and
• $E$ is a antireflexive, symmetric relation on $V$.

In this case, $u$ and $v$ are adjacent if and only if $\left(u, v\right) \in E$ (equivalently, $\left(v, u\right) \in E$).

We say $\left(u, v\right)$ and $\left(v, u\right)$ denote the same edge, and that this edge is incident to $u$ and $v$.

Notes

A graph is sometimes also called a simple graph, to avoid confusion with multigraphs.

Generalizations

A graph as defined here is a special case of several other definitions:

• A graph is a multigraph with no loops and no parallel edges.
• A graph is a hypergraph where every hyperedge has degree 2.