Talk:Graphic matroid

Forests[edit]

As I understand the proof in the second paragraph of the page, that the forests in a graph indeed form a matroid, the "forests" mentioned in the opening paragraph must be spanning forests in the sense that they include every vertex in the graph, while the "spanning forests" said to be the bases of graphical matroids, in the third paragraph, must be spanning forests in the sense of comprising a spanning tree for each component of the graph, which type of spanning forest is, according to this page [[1]], called a "full spanning forest" by Gross and Yellen, and a "maximal spanning forest" by Bondy and Murty. Am I right on these points, and if so, should the page be edited accordingly ? Jumpers for goalposts, enduring image (talk) 17:34, 2 January 2021 (UTC)[reply]

The difference between spanning forests in the first sense you mention, and other forests that are not spanning, is only in the vertices they include with no edges attached. But vertices are irrelevant in the matroid; only the edge set matters. So the distinction you are trying to make is irrelevant here. —David Eppstein (talk) 19:44, 2 January 2021 (UTC)[reply]

Thank you very much David Eppstein for taking time out to respond to my comment on this nice article. I was thinking of the line "It also satisfies the exchange property: if A and B are both forests, and A has more edges than B, then it has fewer connected components". It seems to me that this assertion is generally true only if forests are understood to be spanning in that first sense (i.e. as subgraphs of the original graph, that include all the vertices of the original graph). With that understanding, we can count the edges of the forest by summing over all components of the forest, the number of vertices in that component minus one. Separating the sum into the difference of two sums, this becomes the number of vertices in the original graph, minus the number of components of the forest. Therefore a forest having more edges than another forest must have fewer components than that other forest. Whereas, without the understanding that forests are spanning (in the first sense), the following example doesn't work: Suppose that a forest means an acyclic subgraph of the original graph (its vertex set not necessarily being the whole of the vertex set of the original graph). Consider the graph on vertices 1, 2, 3, 4 and 5, with edges (1, 2), (2, 3) and (4, 5). Let A be the forest with vertices 1, 2 and 3 and edges (1, 2) and (2, 3), and let B be the forest with vertices 4 and 5, and edges (4, 5) (these tiny forests happen to be trees themselves). Then A has more edges than B, but A and B both have the same number of components, viz. 1. Jumpers for goalposts, enduring image (talk) 00:24, 3 January 2021 (UTC)[reply]

Right, to correctly count connected components as described in this sentence, you do need to include the isolated vertices as components. —David Eppstein (talk) 00:26, 3 January 2021 (UTC)[reply]

Many thanks again, David Eppstein. I think I understand now - you mean that a forest that omits some vertices of the original graph can always be supposed to include all such vertices as isolated vertices, without altering its number of edges; for example, for the purpose of the given proof of the exchange property ? Also, is my second point correct, in my first paragraph above, that the bases must be spanning forests in the sense of having a single component per component of the original graph, and if so, is it worth specifying this and providing the link I gave ? Jumpers for goalposts, enduring image (talk) 01:50, 3 January 2021 (UTC)[reply]

Where it currently says that the bases are spanning forests, we could say "full spanning forests" with the same link, to avoid any ambiguity. I don't think adding more than that is necessary. —David Eppstein (talk) 05:22, 3 January 2021 (UTC)[reply]

That sounds great. I have taken the liberty of making this very small change. I see, as you point out, that the link is already there. Thanks once again for your valuable time David Eppstein. Jumpers for goalposts, enduring image (talk) 03:15, 4 January 2021 (UTC)[reply]