Editing Regular icosahedron (section)

== Icosahedral graph ==
[[File:Icosahedron graph.svg|thumb|right|Icosahedral graph]]
Every [[Platonic graph]], including the '''icosahedral graph''', is a [[polyhedral graph]]. This means that they are [[Planar graph|planar graphs]], graphs that can be drawn in the plane without crossing its edges; and they are [[K-vertex-connected graph|3-vertex-connected]], meaning that the removal of any two of its vertices leaves a connected subgraph. According to [[Steinitz theorem]], the icosahedral graph endowed with these heretofore properties represents the [[Skeleton (topology)|skeleton]] of a regular icosahedron.{{sfn|Bickle|2020|p=[https://books.google.com/books?id=2sbVDwAAQBAJ&pg=PA147 147]}}

The icosahedral graph has twelve vertices, the same number of vertices as a regular icosahedron. These vertices are connected by five edges from each vertex, making the icosahedral graph [[Regular graph|5-regular]].{{sfn|Fallat|Hogben|2014|loc=Section 46|p=[https://books.google.com/books?id=8hnYCwAAQBAJ&pg=SA46-PA29 29]}} The icosahedral graph is [[Hamiltonian graph|Hamiltonian]], because it has a cycle that can visit each vertex exactly once.{{sfn|Hopkins|2004}} Any subset of four vertices has three connected edges, with one being the central of all of those three, and the icosahedral graph has no [[induced subgraph]], a [[claw-free graph]].{{sfn|Chudnovsky|Seymour|2005}}

The icosahedral graph is a [[graceful graph]], meaning that each vertex can be labeled with an [[integer]] between 0 and 30 inclusive, in such a way that the [[absolute difference]] between the labels of an edge's two vertices is different for every edge.{{sfn|Gallian|1998}}