Theorem A lists some well-known general properties of bipartite graphs (see, e.g., Spectra of p.87). Graphs, Theorem A. Let B denote a bipartite graph on n vertices. Observation 1. where and . Observation 2. The collection of eigenvalues of B, which are all real, is symmetric with respect to the zero point of the real axis. Observation 3. If then where the product is taken over all non-negative eigenvalues of B. The following theorem is a special case of a result obtained by I. Gutman and N. D.M. Cvetković, in 1974 (Graph ; see Trinajstić theory and molecular orbitals, VII. The role of resonance structures Theorem 8.13 on page 243; see also H. Sachs); it also follows from a general Spectra of Graphs, theorem due to P.W. Kasteleyn (Dimer see also Kasteleyn's statistics and phase transition(1963)); survey article(1967). Orginally formulated for connected graphs, the theorem immediately extends to non-connected graphs, too. Theorem B. Let G be a plane graph on n vertices all of whose finite faces are hexagons. Then G is bipartite and the number of perfect matchings of G is equal to the product of all non-negative eigenvalues of G. Corollary. If G has a perfect matching then . For the next theorem H. Sachsand L. Spialter(1964); see Spectra of (the “coefficients theorem”, Theorem 1.3 on page 32) we need another concept. Graphs, A of a graph is a (not necessarily induced) subgraph that has only circuits and basic figure U dumbbells as its components (Fig. 5). Let and denote the number of components of , and the number of circuits among these components, respectively. Theorem C. Let G be an arbitrary graph with characteristic polynomial . Then , where the sum is taken over all basic figures U of G on precisely i vertices.
Theorem A lists some well-known general properties of bipartite graphs (see, e.g., Spectra of Graphs, p.87). Theorem A. Let B denote a bipartite graph on n vertices. Observation 1. where and . Observation 2. The collection of eigenvalues of B, which are all real, is symmetric with respect to the zero point of the real axis. Observation 3. If then where the product is taken over all non-negative eigenvalues of B. The following theorem is a special case of a result obtained by D.M. Cvetković, I. Gutman and N. Trinajstić in 1974 (Graph theory and molecular orbitals, VII. The role of resonance structures ; see Spectra of Graphs, Theorem 8.13 on page 243; see also H. Sachs); it also follows from a general theorem due to P.W. Kasteleyn (Dimer statistics and phase transition(1963)); see also Kasteleyn's survey article(1967). Orginally formulated for connected graphs, the theorem immediately extends to non-connected graphs, too. Theorem B. Let G be a plane graph on n vertices all of whose finite faces are hexagons. Then G is bipartite and the number of perfect matchings of G is equal to the product of all non-negative eigenvalues of G. Corollary. If G has a perfect matching then . For the next theorem (the “coefficients theorem”, H. Sachsand L. Spialter(1964); see Spectra of Graphs, Theorem 1.3 on page 32) we need another concept. A basic figure U of a graph is a (not necessarily induced) subgraph that has only circuits and dumbbells as its components (Fig. 5). Let and denote the number of components of , and the number of circuits among these components, respectively. Theorem C. Let G be an arbitrary graph with characteristic polynomial . Then , where the sum is taken over all basic figures U of G on precisely i vertices.
05_07_john_sachs.docx