Shannon multigraph

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by Vizing (1965), are a special type of triangle graphs, which are used in the field of edge coloring in particular.

More precisely one speaks of Shannon multigraph Sh(n), if the three vertices are connected by

This multigraph has maximum degree n. Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is

According to a theorem of Shannon (1949), every multigraph with maximum degree

has an edge coloring that uses at most

is even, the example of the Shannon multigraph with multiplicity

shows that this bound is tight: the vertex degree is exactly

edges is adjacent to every other edge, so it requires

colors in any proper edge coloring.

A version of Vizing's theorem (Vizing 1964) states that every multigraph with maximum degree

Again, this bound is tight for the Shannon multigraphs.

This nine-edge Shannon multigraph requires nine colors in any edge coloring; its vertex degree is six and its multiplicity is three.