An undirected graph or graph \(G\) is a triple \(G:=(V,E,\gamma)\) with the following properties:
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\)).
| | | | | created: 2014-03-12 09:24:20 | modified: 2017-01-11 13:20:12 | by: bookofproofs | references: , 
 Aldous Joan M., Wilson Robin J.: “Graphs and Applications – An Introductory Approach”, Springer, 2000
 Krumke Sven O., Noltemeier Hartmut: “Graphentheoretische Konzepte und Algorithmen”, Teubner, 2005, Auflage 1