Graph Theory Théorie Des Graphes

Abstract

We consider classes of graphs which are easily seen to have many perfect matchings. The class of grid graphs is our main example. We then consider what properties to impose on choosing a subset of vertices A ⊆ V (G) for vertex deletion in a graph G (from such a class) so that the vertex deleted subgraph G− A has a perfect matching. Certain conditions are easy. An even number of vertices must be deleted. If the graph is bipartite then the deleted vertices must have equal numbers from both parts of the bipartition. Also one cannot delete all the neighbours of a given vertex.