Graph Degeneracy

Author

Eric W. Weisstein
January 21, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/GraphDegeneracy.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GraphDegeneracy.html.

©2025 Wolfram Research, Inc. except for portions noted otherwise

GraphDataCountTable

GraphDataCountTable["Degeneracy",{"Alkane"->000012,"AlternatingGroupGraph"->005843,"Andrasfai"->000027,"Antiprism"->010709,"Apollonian"->010701,"Barbell"->000027,"Bishop"->001477,"BlackBishop"->001477,"Book"->007395,"Bruhat"->001477,"Centipede"->000012,"CocktailParty"->005843,"Complete"->001477,"CompleteBipartite"->000027,"CompleteTripartite"->299174,"CrossedPrism"->010701,"Crown"->001477,"CubeConnectedCycle"->010701,"Cycle"->007395,"CycleComplement"->001477,"DorogovtsevGoltsevMendes"->007395,"DoubleCone"->010701,"Empty"->000004,"FibonacciCube"->004526,"Flower"->010701,"Gear"->007395,"Goldberg"->010701,{"Grid",2}->007395,{"Grid",3}->010701,"HalvedCube"->000217,"Hanoi"->007395,"Helm"->010701,"HexagonalGrid"->007395,"Hypercube"->000027,"Keller"->284850,"Ladder"->040000,"LadderRung"->000012,"MiddleLayer"->000027,"MoebiusLadder"->010701,"Mycielski"->380327,"Pan"->007395,"Path"->057427,"Pasechnik"->077591,"PermutationStar"->001477,"PlumemrToft"->010701,"Prism"->010701,"SierpinskiCarpet"->007395,"Star"->057427,"Sunlet"->007395,"TorusGrid"->010709,"Transposition"->000217,"Trapezohedron"->010701,"TriangularHoneycombBishop"->001477,"TriangularHoneycombRook"->001477,"TriangualrSnake"->007395,"Web"->010701,"Wheel"->010701}]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"Degeneracy"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Degeneracy"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Degeneracy"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Degeneracy"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["Degeneracy"]

seq=Table[GraphData[{"Antiprism",n},"Degeneracy"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"Degeneracy"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"Degeneracy"],{n,3,20}]

FindSequenceFunction[seq,n-2]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Degeneracy"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Degeneracy"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"Degeneracy"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Degeneracy"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Degeneracy"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"Degeneracy"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"Degeneracy"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["Degeneracy"]

seq=Table[GraphData[{"Complete",n},"Degeneracy"],{n,30}]

FindSequenceFunction[seq,n]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Degeneracy"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Degeneracy"],{n,20}]

FindSequenceFunction[seq,n]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Degeneracy"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Degeneracy"],
Min[m,n]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Degeneracy"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Degeneracy"],{n,10}]

FindSequenceFunction[seq,n]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Degeneracy"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"Degeneracy"],
k+m+n-Max[k,m,n]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Degeneracy"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"Degeneracy"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["Degeneracy"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"Degeneracy"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["Degeneracy"]

seq=Table[GraphData[{"Cycle",n},"Degeneracy"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Degeneracy"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"Degeneracy"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"Degeneracy"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"Degeneracy"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Degeneracy"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["Degeneracy"]

seq=Table[GraphData[{"Empty",n},"Degeneracy"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"Degeneracy"],{n,15}]

FindSequenceFunction[seq,n]//FullSimplify

Table[Ceiling[n/2],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"Degeneracy"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"Degeneracy"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"Degeneracy"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"Degeneracy"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Degeneracy"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"Degeneracy"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Degeneracy"]

seq=Table[GraphData[{"Grid",{n,n}},"Degeneracy"],{n,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Degeneracy"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Degeneracy"],
Piecewise[{{0,m==n==1},{1,Min[m,n]==1}},2]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Degeneracy"]

seq=Table[GraphData[{"Grid",{n,n,n}},"Degeneracy"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Degeneracy"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Degeneracy"],
Piecewise[{{0,k==m==n==1},{1,k m n==Max[k,m,n]},{2,Min[k,m,n]==1}},3]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

A000217

seq=Table[GraphData[{"HalvedCube",n},"Degeneracy"],{n,10}]

FindSequenceFunction[seq,n]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Degeneracy"],{n,6}]

Helm

seq=Table[GraphData[{"Helm",n},"Degeneracy"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["Degeneracy"]

seq=Table[GraphData[{"Hypercube",n},"Degeneracy"],{n,0,10}]

FindSequenceFunction[seq,n+1]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"Degeneracy"],
m+1
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

A284850

Entity["Graph",{"Keller",n}]["Degeneracy"]

seq=Table[GraphData[{"Keller",n},"Degeneracy"],{n,5}]

FindSequenceFunction[seq,n]

Table[4^n-3^n-n,{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Degeneracy"],{n,20}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"Degeneracy"],
Piecewise[{{0,m==n==1},{1,Min[m,n]==1},{3,Min[m,n]<4}},4]
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Degeneracy"]

seq=Table[GraphData[{"Knight",{n,n}},"Degeneracy"],{n,20}]

Table[Piecewise[{{0,n==1||n==2},{2,n==3||n==4},{3,n==5||n==6}},4],{n,20}]==seq

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Degeneracy"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"Degeneracy"],
3
},{n,10},{m,n}],1],{_,x_,x_}]

KP

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"Degeneracy"],
Piecewise[{{m-1,n==1}},m]
},{n,10},{m,10}],1],{_,x_,x_}]

Ladder

Entity["Graph",{"Ladder",n}]["Degeneracy"]

seq=Table[GraphData[{"Ladder",n},"Degeneracy"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"Degeneracy"],{n,20}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"Degeneracy"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"Degeneracy"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Degeneracy"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Degeneracy"]

seq=Table[GraphData[{"MoebiusLadder",n},"Degeneracy"],{n,3,25}]

Mycielski

A380327

Entity["Graph",{"Mycielski",n}]["Degeneracy"]

seq=Table[GraphData[{"Mycielski",n},"Degeneracy"],{n,11}]

$MachineName

Do[Print[{n,GraphDegeneracy[MycielskiGraph[n]]//Timing}],{n,20}]

MycielskiGraph[17] takes 17+ GB

$MachineName

<<MathWorld`Graphs`

m17=MycielskiGraph[17];//Timing

Through[{VertexCount,EdgeCount}[m17]]

MaxMemoryUsed[]/10^9. GB

Do[Print[{n,GraphDegeneracy[m17,Debug->True]//Timing}],{n,{17}}]

GraphDegeneracy[m17,"InitialSize"->1000,Debug->True]

GraphDegeneracy[m17,"InitialSize"->1025,Debug->True]

seq={0,1,2,3,5,8,12,18,29,44,68,107,169,262,412,657,1027};

FindLinearRecurrence[seq]//Head//Timing

FindSequenceFunction[seq,n]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

Odd

Entity["Graph",{"Odd",n}]["Degeneracy"]

seq=Table[GraphData[{"Odd",n},"Degeneracy"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"Degeneracy"],{n,3,20}]

Pasechnik

A077591

seq=Table[GraphData[{"Pasechnik",n},"Degeneracy"],{n,5}]

FindSequenceFunction[seq,n]//Factor

Path

Entity["Graph",{"Path",n}]["Degeneracy"]

seq=Table[GraphData[{"Path",n},"Degeneracy"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"Degeneracy"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"Degeneracy"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"Degeneracy"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["Degeneracy"]

seq=Table[GraphData[{"Prism",n},"Degeneracy"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Degeneracy"],{n,20}]

FindSequenceFunction[seq,n]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Degeneracy"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Degeneracy"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"Degeneracy"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"Degeneracy"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"Degeneracy"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"Degeneracy"],{n,5}]

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"Degeneracy"],
Piecewise[{{1,m==n==1}},2]
},{n,10},{m,n}],1],{_,x_,x_}]

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"Degeneracy"],{n,10}]

StackedPrism m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedPrism",{m,n}},"Degeneracy"],
Piecewise[{{2,n==1}},3]
},{m,3,8},{n,5}],1],{_,x_,x_}]

StackedPrism n×n

seq=Table[GraphData[{"StackedPrism",{n,n}},"Degeneracy"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["Degeneracy"]

seq=Table[GraphData[{"Star",n},"Degeneracy"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"Degeneracy"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"Degeneracy"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"Degeneracy"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Degeneracy"],{n,3,20}]

Transposition

A000217

Entity["Graph",{"Transposition",n}]["Degeneracy"]

seq=Table[GraphData[{"Transposition",n},"Degeneracy"],{n,6}]

FindSequenceFunction[seq,n]

Binomial[n,2]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["Degeneracy"]

seq=Table[GraphData[{"Trapezohedron",n},"Degeneracy"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Degeneracy"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Degeneracy"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Degeneracy"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Degeneracy"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Degeneracy"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Degeneracy"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Degeneracy"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"Degeneracy"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"Degeneracy"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["Degeneracy"]

seq=Table[GraphData[{"Wheel",n},"Degeneracy"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"Degeneracy"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Degeneracy"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Degeneracy"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Degeneracy"],{n,20}]