Definition:Simple Graph

From ProofWiki
Jump to navigation Jump to search

Definition

A simple graph is a graph which is:

An undirected graph, that is, the edges are defined as doubleton sets of vertices and not ordered pairs
Not a multigraph, that is, there is no more than one edge between each pair of vertices
Not a loop-graph, that is, there are no loops, that is, edges which start and end at the same vertex
Not a weighted graph, that is, the edges are not mapped to a number.


Formal 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 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:

Chartrand-exercise-1-3-15.png

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 known as

Authors whose coverage is less general refer to a simple graph as just a graph.


Also see

  • Results about simple graphs can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Simple_Graph&oldid=683953"