Demostrar que el matroide Cographic es realmente un matroide

Question

Dado un gráfico conectado $G=(V,E)$ definamos $M(G)=(E,I)$ donde $I=\{E'\subseteq E | (V,E\backslash E') \text{ is connected}\}$ .

Al probar $M(G)$ es un Matroide que debemos demostrar:

si $A,B\in I$ y $|B|<|A|$ entonces hay $x\in A\backslash B$ s.t. $B\cup \{x\}\in I$ .

En otras palabras, tenemos dos conjuntos de aristas $A,B$ que puede ser eliminado de $E$ sin hacer $G$ desconectado. Debemos demostrar que si $|B|<|A|$ Hay una ventaja $x$ en $A$ que no está en $B$ que incluso después de eliminar $B$ se pueden eliminar las aristas de G manteniendo su conexión.

Tengo problemas para probar esta última afirmación. ¿Debo buscar una arista específica que pueda funcionar, o formular una afirmación general que lleve a su existencia?

Muchas gracias.

Answer 1

Por comodidad, dejemos que $n = |V|$ . Utilizando $n-1$ bordes para conectar el $n$ nodos, se obtiene un árbol (conectado + sin círculos).

Porque $A \in I$ , lo que significa que $(V, E \text{ \ } A)$ es un gráfico conectado. Por lo tanto, $|E \text{ \ } A| \ge n-1$ (en caso contrario, el gráfico $(V, E \text{ \ } A)$ no se conectaría).

$$|B| < |A| \Rightarrow |E \text { \ } B| > | E \text { \ } A |$$

Por eso, $|E \text{ \ } B| \ge n$ lo que significa que hay al menos un círculo en el gráfico $(V, E \text{ \ } B)$ . Dado que ambos $(V, E \text{ \ } A)$ y $(V, E \text{ \ } B)$ son gráficos conectados, tiene que haber una arista en un círculo en $(V, E \text{ \ } B)$ que no se utiliza en el gráfico $(G, E \text{ \ } A)$ :

$$\exists e \in (E \text{ \ } B): e \notin (E \text{ \ } A) \\ \Leftrightarrow \exists e \in E: (e \notin B) \wedge (e \in A) \\ \Leftrightarrow \exists e \in (A \text{ \ } B) $$

Al poner este borde $e$ en $B$ eliminamos una arista de un círculo en $(V, E \text{ \ } B)$ sin desconectar el gráfico. Por lo tanto, $(B \cup \left\lbrace e \right\rbrace) \in I$ .

$\square$