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 formula_1, formula_1 and formula_3 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 formula_3. Edge coloring. According to a theorem of , every multigraph with maximum degree formula_5 has an edge coloring that uses at most  formula_6 colors. When formula_5 is even, the example of the Shannon multigraph with multiplicity formula_8 shows that this bound is tight: the vertex degree is exactly formula_5, but each of the formula_6 edges is adjacent to every other edge, so it requires formula_6 colors in any proper edge coloring. A version of Vizing's theorem states that every multigraph with maximum degree formula_5 and multiplicity formula_13 may be colored using at most formula_14 colors. Again, this bound is tight for the Shannon multigraphs.