Definition:Simple Graph/Formal Definition
Definition
Let $V$ be a set.
Let $\RR$ be an endorelation on $V$ which is antireflexive and symmetric.
Let $E$ be the set whose elements of the form:
- $\set {\tuple {v_a, v_b}, \tuple {v_b, v_a} }$.
where $\tuple {v_a, v_b}$ and $\tuple {v_b, v_a}$ are elements of $\RR$
A simple graph is an ordered pair $G = \struct {V, E}$, where $V$ and $E$ are defined as above.
$V$ is called the vertex set.
$E$ is called the edge set.
Also presented as
It is often more convenient to express the elements of the edge set of a simple graph as doubletons, of the form $\set {v_a, v_b}$.
Also defined as
Some sources impose the condition that a simple graph must have at least one vertex.
Some sources also define a simple graph as one which has a finite number of vertices.
Examples
Arbitrary Order $4$ Graph
Let $V = \set {v_1, v_2, v_3, v_4}$.
Let $\RR = \set {\tuple {v_1, v_2}, \tuple {v_1, v_3}, \tuple {v_2, v_1}, \tuple {v_2, v_3}, \tuple {v_3, v_1}, \tuple {v_3, v_2}, \tuple {v_3, v_4}, \tuple {v_4, v_3} }$.
Then:
- $E = \set {\set {\tuple {v_1, v_2}, \tuple {v_2, v_1} }, \set {\tuple {v_1, v_3}, \tuple {v_3, v_1} }, \set {\tuple {v_2, v_3}, \tuple {v_3, v_2} }, \set {\tuple {v_3, v_4}, \tuple {v_4, v_3} } }$
Arbitrary Order $5$ Graph
Let $G = \struct {V, E}$ be a simple graph such that:
- $V = \set {v_1, v_2, v_3, v_4, v_5}$
- $E = \set {v_1 v_2, v_1 v_4, v_1 v_5, v_2 v_3, v_3 v_5, v_4 v_5}$
Then $G$ can be presented in diagram form as:
The underlying relation $\RR$ on $V$ which defines the edge set of $G$ is:
- $\RR = \set {\tuple {v_1, v_2}, \tuple {v_2, v_1}, \tuple {v_1, v_4}, \tuple {v_4, v_1}, \tuple {v_1, v_5}, \tuple {v_5, v_1}, \tuple {v_2, v_3}, \tuple {v_3, v_2}, \tuple {v_3, v_5}, \tuple {v_5, v_3}, \tuple {v_4, v_5}, \tuple {v_5, v_4} }$
Also see
- Results about simple graphs can be found here.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs