Paths and cycles concerning independence edges (Q757417): Difference between revisions

A natural generalization of the concept of alternating path for a matching is that of an admissible path. An admissible path or cycle D in a graph G for a set L of pairwise independent edges is one in which, whenever \(e\in L\), D either contains e or touches no vertex of e. This paper gives a necessary and sufficient condition for a connected graph G to have an admissible path connecting two given vertices for such L. An analogous theorem gives the result for the case when g is 2- connected. The proofs require q pages of supplemental concepts and lemmas. Using these results, the author is able to prove Tutte's 1-factor theorem as well as extensions of two theorems of Lovász on admissible cycles. As another application, the author shows that if G is a 3-regular graph with a Hamiltonian cycle H, then, given any edge of H, there is an admissible cycle for \(L=E(G)-E(H)\) in G through that edge.