Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-20T15:14:10.011Z Has data issue: false hasContentIssue false

Connectivity in Matroids

Published online by Cambridge University Press:  20 November 2018

W. T. Tutte*
Affiliation:
University of Waterloo
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

An edge of a 3-connected graph G is called essential if the 3-connection of G is destroyed both when the edge is deleted and when it is contracted to a single vertex. It is known (1) that the only 3-connected graphs in which every edge is essential are the “wheel-graphs.” A wheel-graph of order n, where n is an integer ⩾3, is constructed from an n-gon called its “rim” by adding one new vertex, called the “hub,” and n new edges, or “spokes” joining the new vertex to the n vertices of the rim; see Figure 4A.

A matroid can be regarded as a generalized graph. One way of developing the theory of matroids is therefore to generalize known theorems about graphs. In the present paper we do this with the theorem stated above.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1966

References

1. Tutte, W. T., A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc, 64 (1961), 441455.Google Scholar
2. Tutte, W. T., Lectures on matroids, J. Res. Natl. Bur. Standards, 69B (1965), 147.Google Scholar
3. Tutte, W. T., Menger's theorem for matroids, J. Res. Natl. Bur. Standards, 69B (1965), 4953.Google Scholar
4. Whitney, H., The abstract properties of linear dependence, Amer. J. Math., 57 (1935), 507533.Google Scholar