Published online by Cambridge University Press: 24 October 2008
We refer to a beautiful and important result of Tutte(1), in the theory of graphs; that a linear graph G is prime if and only if it contains a set ∑ of vertices, such that u(G∑) > n(∑); where n(∑) is the number of vertices in ∑, G∑ is the graph obtained from G by deleting the star of ∑ (all the vertices of G in ∑, together with all the edges of G meeting vertices of ∑), and u(G∑) is the number of connected components of G∑ having an odd number of vertices.