Conditions for Graphic Matroids

184 Views Asked by At

Basically, I've been researching chromatic graph theory for an essay and have come across this article regarding matroids and their generalisation of graphs. The article in question is here: "http://www.ams.org/journals/notices/201701/rnoti-p26.pdf". What I can't quite seem to understand is how the conditions work for defining a graphic matroid. Using the definition of matroids given on page 27 and the bit after, the article says to construct the graphic matroid of a graph, one defines the ground set as the set of edges of the graph and any flat as a subset of edges such that there doesn't exist an edge on the graph incident on two vertices that are path connected in the flat (i.e. there doesn't exist an edge which, when added to the flat, adds at least one cycle to it). I'm just having trouble in understanding how that condition is sufficient to justifying that the choice of flats always forms a matroid. Well in particular, how does the condition under the choice of edges relate to the axioms which define flats of a matroid?