Examples
Any odd-length cycle graph is factor-critical, as is any complete graph with an odd number of vertices. More generally, every Hamiltonian graph with an odd number of vertices is factor-critical. The friendship graphs (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but not Hamiltonian.
If a graph G is factor-critical, then so is the Mycielskian of G. For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical.
Every 2-vertex-connected claw-free graph with an odd number of vertices is factor-critical. For instance, the 11-vertex graph formed by removing a vertex from the regular icosahedron (the graph of the gyroelongated pentagonal pyramid) is both 2-connected and claw-free, so it is factor-critical. This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.
Read more about this topic: Factor-critical Graph
Famous quotes containing the word examples:
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)