## You are here

Homemultigraph

## Primary tabs

# multigraph

A *multigraph* is a graph in which we allow more than one edge to join a pair of vertices. Two or more edges that join a pair of vertices are called *parallel edges*. Every graph, then, is a multigraph, but not all multigraphs are graphs.
Some authors define the concept of a graph by excluding graphs with multiple
edges or loops. Then if they want to consider more general graphs the term
multigraph is introduced. Usually, such graphs have no loops.
Formally, a multigraph $G=(V,E)$ is a pair, where $E=(V^{{(2)}},f)$
is a multiset for which $f(x,x)=0$ and $V^{{(2)}}$ is the set of unordered pairs
of $V$.

A multigraph can be used to represent a matrix whose entries are nonnegative integers. To do this, suppose that $A=(a_{{ij}})$ is an $m\times n$ matrix of nonnegative integers. Let $V=S\cup T$, where $S=\{1,\ldots,m\}$ and $T=\{1^{{\prime}},\ldots,n^{{\prime}}\}$ and connect vertex $i\in S$ to vertex $j^{{\prime}}\in T$ with $a_{{ij}}$ edges.

## Mathematics Subject Classification

05C75*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections