Maximum Nullity

Author

Eric W. Weisstein
February 13, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/MaximumNullity.nb.

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

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

Sources

https://arxiv.org/pdf/2506.10726

Determining the minimum rank /maximum nullity of a graph has been studied extensively since [15]. For most graphs mrpGqpequivalently, MpGqqis difficult to compute.

An exact algorithm for calculating the minimum rank of a graph is known, but the number of variables makes the computation cost prohibitive. In [11], a purely combinatorial bound on the maximum nullity was proven:

[15] Peter M Nylen. Minimum-rank matrices with prescribed graph. Linear Algebra and its Applications, 248:303–316, 1996.

[11] AIM Minimum Rank-Special Graphs Work Group et al. Zero forcing sets and the minimum rank of graphs. Linear algebra and its applications, 428(7):1628–1648, 2008.

[8] Laura DeLoss, Jason Grout, Leslie Hogben, Tracy McKay, Jason Smith, and Geoff Tims. Table of minimum ranks of graphs of order at most 7 and selected optimal matrices. arXiv preprint arXiv:0812.0870, 2008.

https://arxiv.org/pdf/0812.0870

/Users/eww/Downloads/0812.0870/data/minrank-without-precomputed.csv

https://aimath.org/WWN/matrixspectrum/catalog2.html

https://aimath.org/pastworkshops/catalog1.html#E

AIM Workshop References

https://web.archive.org/web/20160207084159/http://orion.math.iastate.edu/lhogben/AIMmrgraphcatrefs.pdf

Almodovar et al.

Minimum rank, maximum nullity and zero forcing number for selected graph families
Edgard Almodovar, Laura DeLoss, Leslie Hogben, Kirsten Hogenson,
Kaitlyn Murphy, Travis Peters and Camila A. Ramírez

https://projecteuclid.org/journals/involve-a-journal-of-mathematics/volume-3/issue-4/Minimum-rank-maximum-nullity-and-zero-forcing-number-for-selected/10.2140/involve.2010.3.371.pdf

[AD+10] E. Almodovar, L. DeLoss, L. Hogben, K. Hogenson, K. Murphy, T. Peters, and C. Ram´ırez. Minimum rank, maximum nullity and zero forcing number, and spreads of these parameters for selected graph families. Involve, 3: 371–392, 2010.

AIM Minimum Rank—Special Graphs Work Group

AIM Minimum Rank—Special Graphs Work Group.  "Zero forcing sets and the minimum rank of graphs."  Linear Algebra and its Applications 428, 1628–1648, 2008.  https://draganstevanovic.wordpress.com/wp-content/uploads/2012/09/published-version2.pdf?utm_source=chatgpt.com

GraphDataCountTable

table=GraphDataCountTable["MaximumNullity"]

DateString[]

TextGrid[OEISUpdates[table],Dividers->All]

Parametrized families

<<MathWorld`Graphs`

Alkane

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

AlternatingGroupGraph

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

Andrasfai

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

Antelope n×n

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

Antiprism

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

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

AIM Minimum Rank—Special Graphs Work Group.  "Zero forcing sets and the minimum rank of graphs."  Linear Algebra and its Applications 428, 1628–1648, 2008.  https://draganstevanovic.wordpress.com/wp-content/uploads/2012/09/published-version2.pdf?utm_source=chatgpt.com

Apollonian

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

Barbell

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

Bishop n×n

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

BlackBishop n×n

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

Book

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

Bruhat

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

Camel n×n

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

Cameron

seq=Table[GraphData[{"Cameron",n},"MaximumNullity"],{n,20}]

Centipede

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

CocktailParty

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

Complete

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

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

CompleteBipartite n×n

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

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

Table[Piecewise[{{1,n==1}},2(n-1)],{n,20}]

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"MaximumNullity"],
Piecewise[{{1,m==n==1}},m+n-2]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteKPartite

https://aimath.org/WWN/matrixspectrum/catalog2.html

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/compmult

CompleteMultipartiteMinimumRank[parts_List]:=Module[{ns,k,n1,n3},If[!VectorQ[parts,IntegerQ[#]&&#>=1&],Return[Missing["InvalidPartsSizes"]]];
ns=Reverse@Sort[parts];
k=Length[ns];
n1=ns[[1]];
n3=If[k>=3,ns[[3]],0];
Which[k==1,0,n1==1,1,k>=3&&n3>=3,3,True,2]]

CompleteMultipartiteMaximumNullity[parts_List]:=Module[{mr},mr=CompleteMultipartiteMinimumRank[parts];
If[IntegerQ[mr],Total[parts]-mr,mr]]

new=DeleteCases[
{#,parts=GraphData[#,"NotationRules","CompleteKPartite"],CompleteMultipartiteMaximumNullity[parts],GraphData[#,"MaximumNullity"]}&/@GraphData["CompleteKPartite"],
{_,_,x_,x_}]

CompleteTripartite n×n×n

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

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

Table[Piecewise[{{2,n==1},{4,n==2}},3 (n-1)],{n,10}]

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"MaximumNullity"],
k+m+n-Piecewise[{{1,Max[k,m,n]==1},{3,Min[k,m,n]>=3}},2]
},{n,10},{m,n},{k,m}],2],
{_,x_,x_}]

CossidentePenttila

seq=Table[GraphData[{"CossidentePenttila",n},"MaximumNullity"],{n,10}]

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

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

Cycle

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

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

MaximumNullity[CycleGraph[3]]

MaximumNullity[CycleGraph[4]]

CycleComplement

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

DiagonalIntersection

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

Dipyramid

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

DorogovtsevGoltsevMendes

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

DoubleCone

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

Empty

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

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

ErectedPolygon

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/pathstrongprod

FibonacciCube

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

Fiveleaper n×n

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

Flower

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

FoldedCube

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

Gear

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

Giraffe n×n

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

Goldberg

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

Grid n×n

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

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

Grid m×n

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"MaximumNullity"],
Min[m,n]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"MaximumNullity"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

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

Helm

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

Hypercube

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

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

Table[Piecewise[{{0,n==0}},(2^(n-1))],{n,0,10}]

KC

https://aimath.org/WWN/matrixspectrum/catalog2.html

DeleteCases[
With[{gn=#,t=#2,s=#3},{gn,2t,GraphData[gn,"MaximumNullity"]}]&@@@DeleteCases[
{#,Sequence@@GraphData[#,"NotationRules","KC"]}&/@GraphData["KC"],
{_,_,_?(LessThan[4])}
],
{_,x_,x_}]

Keller

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

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

King m×n

https://aimath.org/WWN/matrixspectrum/catalog2.html

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"MaximumNullity"],
Piecewise[{{1,Min[m,n]==1}},m+n-1]
},{n,10},{m,n}],1],{_,x_,x_}]

King n×n

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

FindSequenceFunction[seq,n]

Knight n×n

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

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

Knight m×n

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

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

KP

https://aimath.org/WWN/matrixspectrum/catalog2.html

DeleteCases[
With[{gn=#,s=#2,t=#3},{gn,s,GraphData[gn,"MaximumNullity"]}]&@@@DeleteCases[
{#,Sequence@@GraphData[#,"NotationRules","KP"]}&/@GraphData["KP"],
{_,_,1}
],
{_,x_,x_}]

Ladder

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

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

Table[Piecewise[{{1,n==1}},2],{n,20}]

LadderRung

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

LindgrenSousselier

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

LucasCube

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

MengerSponge

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

MoebiusLadder

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

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

Mycielski

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

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

Necklace

seq=Table[GraphData[{"Necklace",n},"MaximumNullity"],{n,10}]

Table[n+2,{n,10}]

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/neck

https://aimath.org/WWN/matrixspectrum/catalog2.html

[DG+09] L. DeAlba, J. Grout, L. Hogben, R. Mikkelson, and K. Rasmussen. Universally optimal matrices and field independence of the minimum rank of a graph. Elec. J. Lin. Alg., 18: 403–419, 2009.

Odd

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

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

Paley

seq=Table[GraphData[{"Paley",n},"MaximumNullity"],{n,XXX}]

Pan

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

Path

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

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

PathComplement

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

Peisert

seq=Table[GraphData[{"Peisert",n},"MaximumNullity"],{n,XXX}]

Pell

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

Pineapple

new=With[{gn=#,m=#2[[1]],k=#2[[2]]},{gn,k+m-3,GraphData[gn,"MaximumNullity"]}]&@@@DeleteCases[
{#,GraphData[#,"NotationRules","Pineapple"]}&/@GraphData["Pineapple"],
{_,{_,1}}
]

DeleteCases[new,{_,x_,x_}]

https://aimath.org/WWN/matrixspectrum/catalog2.html

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/crciclo

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/view/_id/5303cb962d62b7385f0be323

[DG+09] L. DeAlba, J. Grout, L. Hogben, R. Mikkelson, and K. Rasmussen. Universally optimal matrices and field independence of the minimum rank of a graph. Elec. J. Lin. Alg., 18: 403–419, 2009.

PlummerToft

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

Prism

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

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

Table[Piecewise[{{3,n==3}},4],{n,3,25}]

Queen n×n

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

Rook m×n

https://aimath.org/WWN/matrixspectrum/catalog2.html

DeleteCases[With[{gn=#,s=#2,t=#3},{gn,s t-s-t+2,GraphData[gn,"MaximumNullity"]}]&@@@DeleteCases[
{#,Sequence@@GraphData[#,"NotationRules","Rook"]}&/@GraphData["Rook"],
{_,1,_}],
{_,x_,x_}]

Rook n×n

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

FindSequenceFunction[seq,n]//FullSimplify

RookComplement n×n

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

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

Spoke n×n

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

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"MaximumNullity"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

StackedBook n×n

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

StackedPrism m×n

https://aimath.org/WWN/matrixspectrum/catalog2.html

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

StackedPrism n×n

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

Star

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

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

Table[Piecewise[{{1,n==1||n==2}},n-2],{n,25}]

Sun

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

Sunlet

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

Tetrahedral

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

TorusGrid m×n

http://admin.aimath.org/resources/graph-invariants/minimumrankoffamilies/#/pathstrongprod

DeleteCases[With[{gn=#,s=#2,t=#3},{gn,If[t==s&&OddQ[s],2s-1,2s],GraphData[gn,"MaximumNullity"]}]&@@@(
{#,Sequence@@GraphData[#,"NotationRules","TorusGrid"]}&/@GraphData["TorusGrid"]),
{_,x_,x_}]

TorusGrid n×n

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

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Transposition

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

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

Trapezohedron

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

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

Tree

https://aimath.org/WWN/matrixspectrum/catalog2.html

Triangular

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

TriangularGrid

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

https://aimath.org/WWN/matrixspectrum/catalog2.html

mth supertriangle = {"TriangularGrid", m-1}

GraphData[{"TriangularGrid",2}]

Table[GraphData[{"TriangularGrid",n},"V"],{n,10}]

Table[(1/2)(n+1)(n+2),{n,10}]

Table[GraphData[{"TriangularGrid",n},"Diameter"],{n,10}]

Table[n,{n,10}]

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

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

TriangularHoneycombRook

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

TriangularSnake

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

Unicyclic

https://aimath.org/WWN/matrixspectrum/catalog2.html

Web

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

Wheel

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

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

WheelComplement

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

WhiteBishop n×n

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

WhiteCamel n×n

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

Zebra n×n

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

Algorithm

V? 5 s

data=DeleteCases[Monitor[
{
#,
Check[TimeConstrained[MaximumNullity[GraphData[gn=#]],5],Print[#]],
GraphData[#,"MaximumNullity"]
}&/@SortBy[GraphData[;;5],GraphData[#,"V"]&],
gn],
{_,x_,x_}]

Cases[data,{gn_,$Aborted,_}:>gn]

DeleteCases[data,{gn_,_,_Missing}]

MaximumNullity[Graph[{1},{}]]//Timing

MinimumRank[Graph[{1},{}]]//Timing

MinimumRank[StarGraph[5]]//Timing

MinimumRank[GraphData["GemGraph"]]//Timing

MinimumRank[GraphData["HouseGraph"]]//Timing

AIMathWorkshopMinimumRankCatalog=;

AIMathWorkshopMinimumRankCatalogLookup[gn_,prop__]:=Lookup[Lookup[AIMathWorkshopMinimumRankCatalog,Key@gn],prop]

V5 10 s

(bad=DeleteCases[
data=Monitor[{
gn=#,
TimeConstrained[MaximumNullity[GraphData[#]],10],
AIMathWorkshopMinimumRankCatalogLookup[#,"MaximumNullity"]
}&/@Complement[
GraphData["Connected",2;;6],
{"GemGraph"}
],
gn],
{_,x_,x_}])//Timing

Length[bad]

DeleteCases[bad,{_,$Aborted,_}]

V5 60 s

(bad=DeleteCases[
data=Monitor[{
gn=#,
TimeConstrained[MaximumNullity[GraphData[#]],60],
AIMathWorkshopMinimumRankCatalogLookup[#,"MaximumNullity"]
}&/@Complement[
GraphData["Connected",2;;6],
{"GemGraph"}
],
gn],
{_,x_,x_}])//Timing

Length[bad]

DeleteCases[bad,{_,$Aborted,_}]

V5 300 s

(bad=DeleteCases[
data=Monitor[{
gn=#,
TimeConstrained[MaximumNullity[GraphData[#]],300],
AIMathWorkshopMinimumRankCatalogLookup[#,"MaximumNullity"]
}&/@Complement[
GraphData["Connected",2;;6],
{"GemGraph"}
],
gn],
{_,x_,x_}])//Timing

Length[bad]

DeleteCases[bad,{_,$Aborted,_}]

6v1 300 s

(bad=DeleteCases[
data=Monitor[{
gn=#,
TimeConstrained[MaximumNullity[GraphData[#]],300],
AIMathWorkshopMinimumRankCatalogLookup[#,"MaximumNullity"]
}&/@Complement[
GraphData["Connected",2;;6],
{"GemGraph"}
],
gn],
{_,x_,x_}])//Timing

Length[bad]

DeleteCases[bad,{_,$Aborted,_}]

6v2 300 s

(bad=DeleteCases[
data=Monitor[{
gn=#,
TimeConstrained[MaximumNullity[GraphData[#]],300],
AIMathWorkshopMinimumRankCatalogLookup[#,"MaximumNullity"]
}&/@Complement[
GraphData["Connected",2;;6],
{"GemGraph"}
],
gn],
{_,x_,x_}])//Timing

Length[bad]

DeleteCases[bad,{_,$Aborted,_}]