Types of Edge

  • Distinguish between loops and multigraph and pseudograph.

Consider this graph:


An edge can attach a vertex to itself (like $\{ B,B \}$); this is called a loop. A graph that contains loops is called a pseudograph.

There can be multiple edges (a.k.a parallel edges) between the same end-points (like $\{C,D \}$, which is a double edge). Graphs that have parallel edges are called multigraph.

A simple graph is one where there are no loops or multiple edges.

Exercise What kind of a graph is this?

A) Directed multigraph
B) Directed pseudograph
C) Simple directed graph
D) Simple undirected graph

Solution

A simple directed graph.

The edges between $C$ and $B$ are directed (opposite direction), so it is not multiple-edge; thus not a multigraph.

Aside: Not every vertex has to have an edge attached to it. A vertex with no edges is called an isolated vertex.

A graph that has an isolated vertex is not "connected."

In a connected graph, it is possible to get from every vertex in the graph to every other vertex through a series of edges.