Forbidden Minors
Forming a minor of a pseudoforest by contracting some of its edges and deleting others produces another pseudoforest. Therefore, the family of pseudoforests is closed under minors, and the Robertson–Seymour theorem implies that pseudoforests can be characterized in terms of a finite set of forbidden minors, analogously to Wagner's theorem characterizing the planar graphs as the graphs having neither the complete graph K5 nor the complete bipartite graph K3,3 as minors. As discussed above, any non-pseudoforest graph contains as a subgraph a handcuff, figure 8, or theta graph; any handcuff or figure 8 graph may be contracted to form a butterfly graph (five-vertex figure 8), and any theta graph may be contracted to form a diamond graph (four-vertex theta graph), so any non-pseudoforest contains either a butterfly or a diamond as a minor, and these are the only minor-minimal non-pseudoforest graphs. Thus, a graph is a pseudoforest if and only if it does not have the butterfly or the diamond as a minor. If one forbids only the diamond but not the butterfly, the resulting larger graph family consists of the cactus graphs and disjoint unions of multiple cactus graphs.
More simply, if multigraphs with self-loops are considered, there is only one forbidden minor, a vertex with two loops.
Read more about this topic: Pseudoforest
Famous quotes containing the word forbidden:
“There’s a theory, one I find persuasive, that the quest for knowledge is, at bottom, the search for the answer to the question: “Where was I before I was born.” In the beginning was ... what? Perhaps, in the beginning, there was a curious room, a room like this one, crammed with wonders; and now the room and all it contains are forbidden you, although it was made just for you, had been prepared for you since time began, and you will spend all your life trying to remember it.”
—Angela Carter (1940–1992)