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

- \(V\) is a non-empty set of elements called
**vertices**or**nodes**. - \(E\) is a set (non-empty or empty) of elements, called
**edges**. - Vertices and edges are not the same objects, formally \(V\cap E=\emptyset\).
- 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\)).

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

(none)

[566] **Aldous Joan M., Wilson Robin J.**: “Graphs and Applications – An Introductory Approach”, Springer, 2000

[570] **Krumke Sven O., Noltemeier Hartmut**: “Graphentheoretische Konzepte und Algorithmen”, Teubner, 2005, Auflage 1

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint

© 2018 Powered by BooOfProofs, All rights reserved.

© 2018 Powered by BooOfProofs, All rights reserved.