Why So $C_4 \subseteq C_2$

algebraic-graph-theorycombinatoricsgraph theorymatroids

Here is the question I am trying to understand its solution:

Let $C_1$ and $C_2$ be circuits of a matroid $M$ such that $C_1 \cup C_2 = E(M)$ and $C_1 – C_2 = \{e\}.$ Prove that if $C_3$ is a circuit of $M,$ then either $C_3 = C_1$ or $C_2 – C_1 \subseteq C_3.$

Here is a link to the solution given here in this site:

Property of circuits of a matroid made up of two circuits that differ by one element

The OP gave many steps of the solution as follows:

Either $C_3 = C_1$ or not. If $C_3 = C_1$ we're done, so suppose $C_3 \ne C_1$.

We have $C_3 \subseteq E(M) = C_1 \cup C_2$.

If $C_3 \subseteq C_2$, then by (C2)—the second axiom of circuits—$C_3 = C_2$, which satisfies $C_3 \supseteq C_2 \setminus C_1$, and we're done.

Now suppose $C_3 \nsubseteq C_2$.
This means there is an element $x$ in $C_3$ that is not in $C_2$, which must be in $E(M) \setminus C_2 = (C_1 \cup C_2) \setminus C_2 = C_1$. Hence $x \in C_1 \setminus C_2$, so by hypothesis $x = e$.
Thus we have $e \in C_1 \cap C_3$.
By (C3)—the third axiom of circuits—there is a circuit:
$$ C_4 \subseteq (C_1 \cup C_3) – e = (C_1 – e) \cup (C_3 – e) \subseteq C_2 \cup C_3 $$ (…?)

But then there was an answer posted to complete the steps given by the OP, which is below:

Great effort so far. So $C_4\subseteq (C_1\cup C_3)\setminus e\subseteq C_2$ because we are taking the only element out of $C_2$ and so $C_4=C_2.$ Also, $C_1\setminus \{e\}=C_1\cap C_2$ and so $C_2=(C_1\cap C_2)\cup (C_2\setminus C_1)=C_4\subseteq (C_1\cap C_2)\cup (C_3\setminus \{e\})$ and so $C_2\setminus C_1\subseteq C_3\setminus \{e\}\subseteq C_3.$

My questions about this answer is as follows:

1- Why $(C_1\cup C_3)\setminus e\subseteq C_2$? I draw a venn diagram with $C_3$ taking e from $C_1$ and passing by the intersection between $C_1 $ and $C_3$ and having some part in $C_2,$ does this venn diagram violates anything from the assumptions prior to it?

2- Also, why $C_1\setminus \{e\}=C_1\cap C_2$?

Could someone clarify this questions for me please?

Best Answer

  1. It was shown that if $x\in C_3- C_2$, then $x=\{e\}$, so $C_3-C_2 = \{e\}$, so $C_3 - \{e\} \subseteq C_2$

  2. Clearly, $C_1\setminus\{e\}\subseteq C_1$ and because $C_3-C_2 = \{e\}$, $C_1\setminus\{e\}\subseteq C_2$, so $C_1\setminus\{e\}\subseteq C_1\cap C_2$.

    In the reverse direction, $C_1\cap C_2 \subseteq C_1$, and $e\notin C_1\cap C_2$ so $C_1\cap C_2 \subseteq C_1\setminus \{e\}$.

Related Question