The ubiquitous Petersen graph (Q1198655): Difference between revisions

This paper is an overview of recent results concerning the characterization of the well-known Petersen graph, or other results where this remarkable graph props up. A small selection of these follows: Petersen's graph is the smallest graph in which for any three distinct vertices there is another vertex adjacent to the first but not to the others. Except for Petersen's graph, every 2-connected graph with a least minimum degree 3 contains a cycle of length \(1\pmod 3\). Petersen's graph is the only non-Hamiltonian 2-connected \(k\)-regular graph of order \(2k+3\) or \(2k+4\) \((k>1)\). If \(G\) is a triangle-free graph, the largest bipartite subgraph of which contains exactly 4/5 of the edges of \(G\), then \(G\) is either Petersen's graph or the edge-graph of the dodecahedron.