Welcome guest
You're not logged in.
220 users online, thereof 0 logged in

## Definition: Undirected Graph, Vertices, Edges, Simple Graph

An undirected graph or graph $$G$$ is a triple $$G:=(V,E,\gamma)$$ with the following properties:

1. $$V$$ is a non-empty set of elements called vertices or nodes.
2. $$E$$ is a set (non-empty or empty) of elements, called edges.
3. Vertices and edges are not the same objects, formally $$V\cap E=\emptyset$$.
4. The map $$\gamma: E\mapsto \{X:~X\subseteq V,~1\le|X|\le 2\}$$, assigns to every edge $$e$$ its ends, denoted by $$\gamma(e)$$.

Please note that the ends of an edge $$e$$ can be two different vertices (this is the case if $$|\gamma(e)|=2$$) or one an the same vertex (this is the case if $$|\gamma(e)|=1$$).

If $$|\gamma(e)|=1$$, i.e. if the ends of $$e$$ are the same vertex, the edge $$e$$ is called a loop.

Two edges $$e$$ and $$e’$$ are called parallel or multiple edges if $$\gamma(e)=\gamma(e’)$$, (thus they have the same ends). If additionally $$|\gamma(e)|=1$$, they are called multiple loops.

We call $$G$$ a simple undirected graph (or simple graph), if it has no loops and no parallel edges. A simple graph is written $$G(V,E)$$. An edge of simple graph $$e:=(x,y)$$ is written as $$xy$$ (or $$yx$$).

#### Example graph:

| | | | | created: 2014-03-12 09:24:20 | modified: 2017-01-11 13:20:12 | by: bookofproofs | references: [566], [570]

(none)