About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

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.

multigraph 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.

pseudograph with a loop 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