A combinatorial proof of a theorem of Tutte‡
Published online by Cambridge University Press: 24 October 2008
Extract
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.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 62 , Issue 4 , October 1966 , pp. 683 - 684
- Copyright
- Copyright © Cambridge Philosophical Society 1966
References
REFERENCES
- 2
- Cited by