2.3.2. Connected graphs

A vertex u is said to be connected to a vertex v in a graph G if there exists a u-v path in G.

A graph is connected if every two of its vertices are connected. Otherwise the graph is disconnected.

Theorem 2.10. The relation „connected to" is an equivalence relation on the vertex set of every graph G.

Proof. Let . We need to proof that the „connected to" is

-          Reflexive: x ~ x for all .

-          Transitive: If x ~ y and y ~ z then x ~ z.

-          Symmetric: If x ~ y then y ~ x.

And these are trivial.

Each subgraph induced by the vertices in a resulting equivalence class is called a connected component of G. The number of components of G is denoted by .

In a connected graph G the distance between two vertices u and v is the minimum of the lengths of the u-v paths of G.

Figure 2.8. The distance levels in G from the vertex v1.