Vector Spaces and the Petersen Graph

  • Marcelo H. de Carvalho
  • C. H. C. Little


It is shown that a matching covered graph has an ear decomposition with no more than one double ear if and only if there is no set $S$ of edges such that $|S \cap A|$ is even for every alternating circuit $A$ but $|S \cap C|$ is odd for some even circuit $C$. Two proofs are presented. The first uses vector spaces and the second is constructive. Some applications are also given.

Article Number