Shannon multigraph

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by Vizing (1965),^[1] 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 Sh(n), if the three vertices are connected by ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$, ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$ and ${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$ edges respectively. 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 ${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$.^[2][3]