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 is a pair, where is a multiset for which and is the set of unordered pairs of .

A multigraph can be used to represent a matrix whose entries are nonnegative integers. To do this, suppose that is an matrix of nonnegative integers. Let , where and and connect vertex to vertex with edges.