Pseudograph — Definition, Formula & Examples
A pseudograph is a type of graph that permits both loops (edges connecting a vertex to itself) and multiple edges between the same pair of vertices. It is the most general form of an undirected graph.
A pseudograph is an ordered pair where is a nonempty set of vertices and is a multiset of unordered pairs from , allowing repeated elements (parallel edges) and pairs of the form (loops).
How It Works
In a pseudograph, you place no restrictions on how edges connect vertices. Two vertices can share more than one edge, and any vertex can have an edge that starts and ends at itself. When counting the degree of a vertex, each loop contributes 2 to the degree (since it occupies both endpoints), while each ordinary edge contributes 1. Pseudographs arise naturally when modeling networks where duplicate connections or self-referencing links are possible, such as road networks with multiple routes between cities or web pages that link to themselves.
Worked Example
Problem: A pseudograph G has vertex set V = {a, b, c}. It has two edges between a and b, one loop at a, and one edge between b and c. Find the degree of each vertex.
List edges: The edge multiset is E = {(a,b), (a,b), (a,a), (b,c)}. There are 4 edges total.
Compute degrees: Vertex a: two edges to b contribute 2, and the loop contributes 2, giving degree 4. Vertex b: two edges to a contribute 2, and one edge to c contributes 1, giving degree 3. Vertex c: one edge to b contributes 1, giving degree 1.
Verify with handshaking lemma: The sum of all degrees should equal twice the number of edges.
Answer: deg(a) = 4, deg(b) = 3, deg(c) = 1. The handshaking lemma confirms the result.
Why It Matters
Pseudographs are essential in discrete mathematics and combinatorics courses when studying the most general graph structures. In algebraic graph theory, adjacency matrices and incidence matrices for pseudographs capture information that simpler graph models cannot, making them useful in network analysis and topology.
Common Mistakes
Mistake: Counting a loop as adding only 1 to a vertex's degree.
Correction: A loop contributes 2 to the degree of its vertex, because it uses both "endpoints" at the same vertex. This preserves the handshaking lemma.