Kvadratický graf je graf , jehož všechny vrcholy mají stupeň 4. Jinými slovy, kvadratický graf je 4- regulární graf [1] .
Některé známé grafy jsou kvadratické. Jedná se o grafy jako:
Jakýkoli střední graf je kvadratický rovinný graf a jakýkoli kvadratický rovinný graf je středním grafem dvojice duálních rovinných grafů nebo multigrafů [5] . Uzlové diagramy a spojnicové diagramy jsou také kvadratické rovinné multigrafy , ve kterých vrcholy představují průsečíky diagramu a jsou označeny doplňkovými informacemi, které udávají, které dvě větve uzlu protínají druhou větev v tomto bodě [6] .
Protože míra jakéhokoli vrcholu v kvadratickém grafu je sudá, každý spojený kvadratický graf má Eulerův cyklus . Stejně jako u běžných bipartitních grafů má každý bipartitní kvadratický graf dokonalou shodu . V tomto případě je možný mnohem jednodušší a rychlejší algoritmus porovnávání než u nepravidelných grafů – při výběru jakékoli jiné hrany Eulerova cyklu můžeme získat 2-faktor , který by v tomto případě měl být souborem cyklů, z nichž každý který má sudou délku a každý vrchol grafu se objeví přesně v jednom cyklu. Při volbě jakékoli jiné hrany v těchto cyklech získáme perfektní shodu v lineárním čase . Stejným způsobem lze obarvit okraj grafu čtyřmi barvami v lineárním čase [7] .
Kvadratické grafy mají sudý počet hamiltonovských rozšíření [8] .
Otevřeným problémem je domněnka, zda všechny kvadratické hamiltonovské grafy mají sudý počet hamiltonovských cyklů nebo mají více než jeden hamiltonovský cyklus. Je známo, že pro kvadratické multigrafy je odpověď NE [9] .