A PPA parity theorem about trees in a bipartite graph
2020
Abstract We prove a new PPA parity theorem: Given a bipartite graph G with bipartition ( A , B ) where B is a set of even-degree vertices, and given a tree T ∗ of G containing all of A , such that any vertex of B in T ∗ has degree 2 in T ∗ and such that each vertex of A which is not a leaf of T ∗ is met by an odd number of edges not in T ∗ , then there is an even number of trees of G containing all of A , with degree 0 or 2 at each vertex of B and with the same degree as T ∗ at each vertex of A . This theorem generalizes Berman’s generalization of Thomason’s generalization of Smith’s Theorem.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
1
Citations
NaN
KQI