Interminable Paths and Trails: Extreme Cases
Gabriel Andrew Dirac · Mathematische Nachrichten · 1978
Abstract This paper is concerned with terminable and interminable paths and trails in infinite graphs. It is shown that The only connected graphs which contain no 2 – ∞ way and in which no finite path is terminable are precisely all the 1 – ∞ multiways. The only connected graphs which have no 2 – ∞ trail and in which no finite trail is terminable are precisely all the 1 – ∞ multiways all of whose multiplicities are odd numbers and which have infinitely many bridges. In addition the strucuture of those connected graphs is determined which have a 1 – ∞ trail and in which no 1 – ∞ trail but every finite trail is terminable. In this paper the terminology and notation of a previous paper of the writer [1] and of F. HARARY's book [6] will be used. Furthermore, a graph consisting of the distinct nodes n1,…,nδ (where δ≧1) and of one or more (ni, ni+1)‐edges for i = 1,…, δ – 1 will be called a multiway, and analogously for 1 – ∞ and 2 – ∞ multiways. The number of edges joining ni and ni+1 will be called the (ni,+1)‐multiplicity. Thus a multiway in which each multiplicity is 1 is a way. Multiplicities are allowed to be infinite.