Shannon multigraph
Introduction 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. :''A Shannon multigraph is multigraph with 3 vertices for which either of the following conditions holds:'':*''a) all 3 vertices are connected by the same number of edges. '':*''b) as in a) and one additional edge is added. ''More precisely one speaks of Shannon multigraph , if the three vertices are connected by ,  and  edges respectively. This multigraph has maximum degree . Its multiplicity (the maximum number of edges in a set of edges that all have the same endpoints) is .
Examples   File:Shannon multigraph 2.svg|Sh(2)  File:Shannon multigraph 3.svg|Sh(3)  File:Shannon multigraph 4.svg|Sh(4)  File:Shannon multigraph 5.svg|Sh(5)  File:Shannon multigraph 6.svg|Sh(6)  File:Shannon multigraph 7.svg|Sh(7)
Edge coloring This nine-edge Shannon multigraph requires nine colors in any edge coloring; its vertex degree is six and its multiplicity is three.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.
References **.*.*. *.
External links *Lutz Volkmann: '' Graphen an allen Ecken und Kanten''. Lecture notes 2006, p. 242 (German)