Premium
Concept of a vertex in a matroid and 3‐connected graphs
Author(s) -
Kelmans A. K.
Publication year - 1980
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190040103
Subject(s) - combinatorics , mathematics , discrete mathematics , matroid , oriented matroid , graphic matroid , dual graph , graph isomorphism , planar graph , line graph , graph
The concept of a matroid vertex is introduced. The vertices of a matroid of a 3‐connected graph are in one‐to‐one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3‐connected graphs implies isomorphism. The concept of a vertex of a matroid leads to an equally simple proof of Whitney's theorem on the unique embedding of a 3‐connected planar graph in the sphere. It also leads to a number of new facts about 3‐connected graphs. Thus, consideration of a vertex in a matroid that is the dual of the matroid of a graph leads to a natural concept of a nonseparating cycle of a graph. Whitney's theorem on cyclic isomorphism can be strengthened (even if the nonseparating cycles of a graph are considered, the theorem is found to work) and a new criterion for planarity of 3‐connected graphs is obtained (in terms of nonseparating cycles).