Shannon multigraph


In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by, 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, if the three vertices are connected by, and edges respectively. This multigraph has maximum degree. Its multiplicity is.

Examples

Edge coloring

According to a theorem of, every multigraph with maximum degree has an edge coloring that uses at most colors. When is even, the example of the Shannon multigraph with multiplicity shows that this bound is tight: the vertex degree is exactly, but each of the edges is adjacent to every other edge, so it requires colors in any proper edge coloring.
A version of Vizing's theorem states that every multigraph with maximum degree and multiplicity may be colored using at most colors. Again, this bound is tight for the Shannon multigraphs.