nLab pseudograph




In graph theory a pseudograph is a particular type of graph. A pseudograph is a set of vertices and for each unordered pair of vertices a set of edges between these.

A directed pseudograph is also called a quiver.

The terminology is used in distinction to:

  1. multigraphs, which are like pseudographs but not admitted to have “loops” in the sense of edges between a vertex and itself;

  2. simple graphs, which are multigraphs with at most one edge between any unordered pair of distinct vertices.

Beware that the terminology is not completely consistent across different authors. Some authors may allows loops when they speak of multigraphs.

From yet another perspective, pseudographs are also like small dagger categories with identity morphisms and composition forgotten. Conversely, a small dagger category may be regarded as a pseudograph equipped with extra structure. Formally this is witnessed by a forgetful functor

U:DagCatPseudographU\colon DagCat \to Pseudograph

where Pseudograph is the category of pseudographs and DagCat? is the category of (small strict) dagger categories. Moreover, this forgetful functor has a left adjoint

F:PseudographDagCatF\colon Pseudograph \to DagCat

sending each pseudograph to the free dagger category on that pseudograph.


Slick definition

A pseudograph is a quiver GG with a contravariant quiver homomorphism () :GG op(-)^\dagger:G \to G^\op from GG to the opposite quiver G opG^\op which

  1. is the identity on objects,

  2. is an involution =id G\dagger \circ \dagger = \mathrm{id}_G.

Nuts and bolts definition

A pseudograph is a quiver (E,V,s,t)(E, V, s, t) with a function () :EE(-)^\dagger:E \to E such that for any edge f:Ef:E, s(f)=t(f )s(f) = t(f^\dagger), t(f)=s(f )t(f) = s(f^\dagger), and (f ) =f(f^\dagger)^\dagger = f.

See also


Last revised on May 16, 2022 at 05:32:55. See the history of this page for a list of all contributions to it.