Мультиграфы Шеннона — это мультиграфы с тремя вершинами, для которых выполняется одно из следующих условий:
a) все три вершины соединены одним и тем же числом рёбер.
b) так же, как в a) но добавлено ещё одно дополнительное ребро.
Говоря точнее, граф является мультиграфом Шеннона <math>Sh(n)</math>, если три вершины соединены <math>\left\lfloor \frac{n}{2} \right\rfloor </math>, <math>\left\lfloor \frac{n}{2} \right\rfloor </math> и <math>\left\lfloor \frac{n+1}{2} \right\rfloor </math> рёбрами соответственно. Этот мультиграф имеет максимальную степень <math>n</math>. Его кратность (максимальное число рёбер, имеющих те же самые концы) равна <math>\left\lfloor \frac{n+1}{2} \right\rfloor </math>.
Файл:Multigraph-edge-coloring.svgДля рёберной раскраски мультиграфа Шеннона с девятью рёбрами необходимо девять цветов. Его степень равна шести и его кратность равна трём.
Согласно теореме Шеннона[2], любой мультиграф с максимальной степенью <math>\Delta</math> имеет рёберную раскраску, использующую максимум <math>\frac32\Delta</math> цветов. Если число <math>\Delta</math> чётно, пример мультиграфа Шеннона с кратностью <math>\Delta/2</math> показывает, что эта граница точна: степень вершины в точности равна <math>\Delta,</math> но каждое из <math>\frac32\Delta</math> рёбер сопряжено с любым другим ребром, так что требуется <math>\frac32\Delta</math> цветов для любой правильной рёберной раскраски.
Версия теоремы Визинга[3] утверждает, что любой мультиграф с максимальной степенью <math>\Delta</math> и кратностью <math>\mu</math> можно раскрасить используя не более <math>\Delta+\mu</math> цветов. Снова, эта граница точна для мультиграфов Шеннона.
