**Pseudographs and multigraphs **

These tours use the word *graph* to include graphs in which at most one edge connects any two vertices. Some mathematicians use a broader definition of *graph.*

In the picture to the left, two sets of vertices are connected by more than one edge. *Multigraphs* may include such "parallel" edges. In our terminology a graph is a special kind of multigraph.

Giving the endpoints of an edge in a multigraph may not be enough to distinguish it. Often the edges as well as the vertices are labeled, and a walk is described as an alternating sequence of vertices and edges.

In the picture to the right, an edge connects a vertex to itself. That edge is called a *loop*. Loops are possible in a *pseudograph*. Pseudographs may also include multiple edges between vertices, so multigraphs are special cases of pseudographs.

A formal definition of pseudograph refers to a set of vertices, but the edges are defined as a sequence of pairs of vertices. If the definition called for a set of edges, then no pair of vertices could have more than one edge, because elements can't occur more than once in a set.

Ordinarily, when we use the term *graph,* we are excluding pseudographs and multigraphs. Sometimes, for clarity's sake, we use the term* simple graph* instead of the term
*graph.*

Copyright © 1999-2000 SciMathMN