For a graph $G=(V,E)$ ($V$ set of vertices and $E$ set of edges ), $\mathcal{I}$ is defined as all of the subsets $E´\subseteq E$ where the components of $(V,E´)$ that are connected are simple paths. I want to show that $(E,\mathcal{I})$ does not satisfy the exchange property of a matroid.


I have tried to find an example by drawing two graphs, that is, two graphs with all of the vertices $V$ and where each graph has a set of edges and the edges that are connected are simple paths (no cycles). And I tried to make one graph have more edges than the other and find an example where we can NOT add an edge that is in the graph with more edges (but not in the graph with less edges) to the graph with less edges. I always find an edge that can be added.


But I can not find such an example and I am stuck. Maybe there is a simpler way to prove it?



Prove that a definition of $\mathcal{I}$ does not satisfy the exchange property
Take two paths $1234,5678$. Assume that there are no edges between their endpoints (so that you can not enlarge this independent set of 6 edges) but there exists a Hamiltonian path, say 13657428. You get two inclusion-maximal subsets of different size, thus it is not a matroid.


