title: Shannon multigraph
text: # 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.
  
      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 $\left\lfloor {\frac {n}{2}}\right\rfloor$, $\left\lfloor {\frac {n}{2}}\right\rfloor$ and $\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 $\left\lfloor {\frac {n+1}{2}}\right\rfloor$.
  
  ## Examples
  
  * Shannon multigraphs
  * Sh(2)
  * Sh(3)
  * Sh(4)
  * Sh(5)
  * Sh(6)
  * Sh(7)
  
  ## Edge coloring
  
  According to a theorem of Shannon (1949), every multigraph with maximum degree $\Delta$ has an edge coloring that uses at most ${\frac {3}{2}}\Delta$ colors. When $\Delta$ is even, the example of the Shannon multigraph with multiplicity $\Delta /2$ shows that this bound is tight: the vertex degree is exactly $\Delta$, but each of the ${\frac {3}{2}}\Delta$ edges is adjacent to every other edge, so it requires ${\frac {3}{2}}\Delta$ colors in any proper edge coloring.
  
  A version of Vizing's theorem (Vizing 1964) states that every multigraph with maximum degree $\Delta$ and multiplicity $\mu$ may be colored using at most $\Delta +\mu$ colors. Again, this bound is tight for the Shannon multigraphs.
  
  