Premium
Parity theorems for paths and cycles in graphs
Author(s) -
Bondy J. A.,
Halberstam F. Y.
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100113
Subject(s) - mathematics , combinatorics , vertex (graph theory) , parity (physics) , discrete mathematics , graph , physics , particle physics
We extend an elegant proof technique of A. G. Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree has an even number of paths if and only if its order is a multiple of four. Our results have implications for generalized friendship graphs and their conjectured nonexistence.