Gráfico dual

Un gráfico de dipolo

Un gráfico cíclico

La incrustación planar única de un grafo cíclico divide el plano en solo dos regiones, el interior y el exterior del ciclo, según el teorema de la curva de Jordan . Sin embargo, en un n -ciclo, estas dos regiones están separadas entre sí por n aristas diferentes. Por lo tanto, el grafo dual del n -ciclo es un multigrafo con dos vértices (duales a las regiones), conectados entre sí por n aristas duales. Dicho grafo se denomina grafo de aristas múltiples, grafo de enlace o, a veces, grafo dipolar . A la inversa, el dual de un grafo dipolar de n aristas es un n- ciclo. ^{[ 1 ]}

Según el teorema de Steinitz , todo grafo poliédrico (el grafo formado por los vértices y las aristas de un poliedro convexo tridimensional ) debe ser planar y 3-conexo por vértices , y todo grafo planar 3-conexo por vértices se obtiene a partir de un poliedro convexo de esta manera. Todo poliedro convexo tridimensional tiene un poliedro dual ; el poliedro dual tiene un vértice por cada cara del poliedro original, con dos vértices duales adyacentes cuando las dos caras correspondientes comparten una arista. Siempre que dos poliedros son duales, sus grafos también lo son. Por ejemplo, los sólidos platónicos se presentan en pares duales: el octaedro es dual del cubo, el dodecaedro es dual del icosaedro y el tetraedro es dual de sí mismo. ^{[ 2 ]} La dualidad de poliedros también puede extenderse a la dualidad de politopos de dimensiones superiores , ^{[ 3 ]} pero esta extensión de la dualidad geométrica no tiene conexiones claras con la dualidad de la teoría de grafos.

Se dice que un grafo plano es autodual si es isomorfo a su grafo dual. Los grafos de rueda proporcionan una familia infinita de grafos autoduales provenientes de poliedros autoduales (las pirámides ). ^{[ 4 ] [ 5 ]} Sin embargo, también existen grafos autoduales que no son poliédricos, como el que se muestra. Servatius y Christopher (1992) describen dos operaciones, adhesión y explosión, que pueden usarse para construir un grafo autodual que contenga un grafo plano dado; por ejemplo, el grafo autodual mostrado puede construirse como la adhesión de un tetraedro con su dual. ^{[ 5 ]}

De la fórmula de Euler se deduce que todo grafo autodual con n vértices tiene exactamente 2 n − 2 aristas. ^{[ 6 ]} Todo grafo planar autodual simple contiene al menos cuatro vértices de grado tres, y toda incrustación autodual tiene al menos cuatro caras triangulares. ^{[ 7 ]}

El dual de un grafo simple no tiene por qué ser simple: puede tener auto-bucles (una arista con ambos extremos en el mismo vértice) o múltiples aristas que conectan los mismos dos vértices, como ya se evidenció en el ejemplo de los multigrafos dipolares que son duales a los grafos cíclicos. Como caso especial de la dualidad corte-ciclo que se analiza más adelante, los puentes de un grafo planar G están en correspondencia biunívoca con los auto-bucles del grafo dual. ^{[ 9 ]} Por la misma razón, un par de aristas paralelas en un multigrafo dual (es decir, un ciclo de longitud 2) corresponde a un conjunto de corte de 2 aristas en el grafo primal (un par de aristas cuya eliminación desconecta el grafo). Por lo tanto, un grafo planar es simple si y solo si su dual no tiene conjuntos de corte de 1 o 2 aristas; es decir, si es 3-arista-conexo . Los grafos planares simples cuyos duales son simples son precisamente los grafos planares simples 3-arista-conexos. ^{[ 10 ]} Esta clase de grafos incluye, pero no es la misma que, la clase de grafos planares simples con 3 vértices conexos . Por ejemplo, la figura que muestra un grafo autodual tiene 3 aristas conexas (y por lo tanto su dual es simple) pero no tiene 3 vértices conexos.

Debido a que el grafo dual depende de una incrustación particular, el grafo dual de un grafo planar no es único, en el sentido de que el mismo grafo planar puede tener grafos duales no isomorfos . ^{[ 11 ]} En la imagen, los grafos azules son isomorfos, pero sus grafos duales rojos no lo son. El grafo dual rojo superior tiene un vértice con grado 6 (que corresponde a la cara exterior del grafo azul), mientras que en el grafo rojo inferior todos los grados son menores que 6.

Hassler Whitney demostró que si el grafo es 3-conexo , entonces la incrustación, y por lo tanto el grafo dual, es único. ^{[ 12 ]} Según el teorema de Steinitz , estos grafos son exactamente los grafos poliédricos , los grafos de poliedros convexos. Un grafo planar es 3-conexo por vértices si y solo si su grafo dual es 3-conexo por vértices. Además, un grafo biconexo planar tiene una incrustación única, y por lo tanto también un dual único, si y solo si es una subdivisión de un grafo planar 3-conexo por vértices (un grafo formado a partir de un grafo planar 3-conexo por vértices reemplazando algunas de sus aristas por caminos). ^{[ 13 ]} Para algunos grafos planares que no son 3-conexos por vértices, como el grafo bipartito completo K _2,4 , la incrustación no es única, pero todas las incrustaciones son isomorfas. Cuando esto sucede, en consecuencia, todos los grafos duales son isomorfos.

Debido a que diferentes incrustaciones pueden dar lugar a diferentes grafos duales, probar si un grafo es dual de otro (sin conocer previamente sus incrustaciones) es un problema algorítmico no trivial . Para grafos biconexos, se puede resolver en tiempo polinomial utilizando los árboles SPQR de los grafos para construir una forma canónica para la relación de equivalencia de tener un dual mutuo compartido. Por ejemplo, los dos grafos rojos de la ilustración son equivalentes según esta relación. Sin embargo, para grafos planares que no son biconexos, esta relación no es una relación de equivalencia y el problema de probar la dualidad mutua es NP-completo . ^{[ 14 ]}

Un conjunto de corte en un grafo conexo arbitrario es un subconjunto de aristas definido a partir de una partición de los vértices en dos subconjuntos, incluyendo una arista en el subconjunto cuando tiene un extremo en cada lado de la partición. Eliminar las aristas de un conjunto de corte necesariamente divide el grafo en al menos dos componentes conexas. Un conjunto de corte mínimo (también llamado enlace) es un conjunto de corte con la propiedad de que cada subconjunto propio del conjunto de corte no es a su vez un corte. Un conjunto de corte mínimo de un grafo conexo necesariamente separa su grafo en exactamente dos componentes, y consiste en el conjunto de aristas que tienen un extremo en cada componente. ^{[ 15 ]} Un ciclo simple es un subgrafo conexo en el que cada vértice del ciclo es incidente a exactamente dos aristas del ciclo. ^{[ 16 ]}

En un grafo planar conexo G , cada ciclo simple de G corresponde a un conjunto de corte mínimo en el dual de G , y viceversa. ^{[ 17 ]} Esto puede verse como una forma del teorema de la curva de Jordan : cada ciclo simple separa las caras de G en caras en el interior del ciclo y caras en el exterior del ciclo, y los duales de las aristas del ciclo son precisamente las aristas que cruzan del interior al exterior. ^{[ 18 ]} La circunferencia de cualquier grafo planar (el tamaño de su ciclo más pequeño) es igual a la conectividad de aristas de su grafo dual (el tamaño de su conjunto de corte más pequeño). ^{[ 19 ]}

Esta dualidad se extiende desde los conjuntos de cortes y ciclos individuales hasta los espacios vectoriales definidos a partir de ellos. El espacio de ciclos de un grafo se define como la familia de todos los subgrafos que tienen grado par en cada vértice; puede verse como un espacio vectorial sobre el cuerpo finito de dos elementos , donde la diferencia simétrica de dos conjuntos de aristas actúa como la operación de suma vectorial en el espacio vectorial. De manera similar, el espacio de cortes de un grafo se define como la familia de todos los conjuntos de cortes, con la suma vectorial definida de la misma manera. Entonces, el espacio de ciclos de cualquier grafo planar y el espacio de cortes de su grafo dual son isomorfos como espacios vectoriales. ^{[ 20 ]} Por lo tanto, el rango de un grafo planar (la dimensión de su espacio de cortes) es igual al número ciclotómico de su dual (la dimensión de su espacio de ciclos) y viceversa. ^{[ 11 ]} Una base de ciclos de un grafo es un conjunto de ciclos simples que forman una base del espacio de ciclos (cada subgrafo de grado par puede formarse de una sola manera como una diferencia simétrica de algunos de estos ciclos). Para grafos planares ponderados por aristas (con pesos suficientemente generales como para que no haya dos ciclos con el mismo peso), la base de ciclos de peso mínimo del grafo es dual al árbol de Gomory-Hu del grafo dual, una colección de cortes anidados que, en conjunto, incluyen un corte mínimo que separa cada par de vértices del grafo. Cada ciclo en la base de ciclos de peso mínimo tiene un conjunto de aristas que son duales a las aristas de uno de los cortes del árbol de Gomory-Hu. Cuando los pesos de los ciclos pueden estar empatados, la base de ciclos de peso mínimo puede no ser única, pero en este caso sigue siendo cierto que el árbol de Gomory-Hu del grafo dual corresponde a una de las bases de ciclos de peso mínimo del grafo. ^{[ 20 ]}

En los grafos planares dirigidos, los ciclos dirigidos simples son duales a los cortes dirigidos (particiones de los vértices en dos subconjuntos de tal manera que todas las aristas van en una dirección, de un subconjunto al otro). Los grafos planares fuertemente orientados (grafos cuyo grafo subyacente no dirigido es conexo y en los que cada arista pertenece a un ciclo) son duales a los grafos acíclicos dirigidos en los que ninguna arista pertenece a un ciclo. Dicho de otro modo, las fuertes orientaciones de un grafo planar conexo (asignaciones de direcciones a las aristas del grafo que dan como resultado un grafo fuertemente conexo ) son duales a las orientaciones acíclicas (asignaciones de direcciones que producen un grafo acíclico dirigido ). ^{[ 21 ]} De la misma manera, los conjuntos de aristas (conjuntos de aristas que incluyen una arista de cada corte dirigido) son duales a los conjuntos de arcos de retroalimentación (conjuntos de aristas que incluyen una arista de cada ciclo). ^{[ 22 ]}

Un árbol de expansión se define como un conjunto de aristas que, junto con todos los vértices del grafo, forman un subgrafo conexo y acíclico. Sin embargo, por dualidad de corte-ciclo, si un conjunto S de aristas en un grafo planar G es acíclico (no tiene ciclos), entonces el conjunto de aristas duales a S no tiene cortes, de lo cual se deduce que el conjunto complementario de aristas duales (las duales de las aristas que no están en S ) forma un subgrafo conexo. De forma simétrica, si S es conexo, entonces las aristas duales al complemento de S forman un subgrafo acíclico. Por lo tanto, cuando S posee ambas propiedades (es conexo y acíclico), lo mismo ocurre con el conjunto complementario en el grafo dual. Es decir, cada árbol de expansión de G es complementario a un árbol de expansión del grafo dual, y viceversa. Así, las aristas de cualquier grafo planar y su dual pueden particionarse (de múltiples maneras diferentes) en dos árboles de expansión, uno en el grafo primal y otro en el dual, que juntos se extienden a todos los vértices y caras del grafo, pero nunca se cruzan entre sí. En particular, el árbol de expansión mínimo de G es complementario al árbol de expansión máximo del grafo dual. ^{[ 23 ]} Sin embargo, esto no funciona para los árboles de caminos más cortos , ni siquiera de forma aproximada: existen grafos planares tales que, para cada par formado por un árbol de expansión en el grafo y un árbol de expansión complementario en el grafo dual, al menos uno de los dos árboles tiene distancias significativamente mayores que las distancias en su grafo. ^{[ 24 ]}

Un ejemplo de este tipo de descomposición en árboles entrelazados se puede observar en algunos tipos simples de laberintos , con una sola entrada y sin componentes desconectados en sus paredes. En este caso, tanto las paredes del laberinto como el espacio entre ellas adoptan la forma de un árbol matemático. Si el espacio libre del laberinto se divide en celdas simples (como los cuadrados de una cuadrícula), este sistema de celdas puede considerarse una incrustación de un grafo planar, en el que la estructura arbórea de las paredes forma un árbol de expansión del grafo y la estructura arbórea del espacio libre forma un árbol de expansión del grafo dual. ^{[ 25 ]} Pares similares de árboles entrelazados también se pueden observar en el patrón arbóreo de arroyos y ríos dentro de una cuenca hidrográfica y en el patrón arbóreo dual de crestas que separan los arroyos. ^{[ 26 ]}

Esta partición de las aristas y sus duales en dos árboles conduce a una demostración simple de la fórmula de Euler V − E + F = 2 para grafos planares con V vértices, E aristas y F caras. Cualquier árbol de expansión y su árbol de expansión dual complementario particionan las aristas en dos subconjuntos de V − 1 y F − 1 aristas respectivamente, y sumando los tamaños de los dos subconjuntos se obtiene la ecuación

E = ( V − 1) + ( F − 1)

que puede reordenarse para formar la fórmula de Euler. Según Duncan Sommerville , esta demostración de la fórmula de Euler se debe a la obra Geometrie der Lage (Núremberg, 1847) de KGC Von Staudt . ^{[ 27 ]}

En las incrustaciones de superficies no planas, el conjunto de aristas duales complementarias a un árbol de expansión no es un árbol de expansión dual. En cambio, este conjunto de aristas es la unión de un árbol de expansión dual con un pequeño conjunto de aristas adicionales cuyo número está determinado por el género de la superficie sobre la que se incrusta el grafo. Las aristas adicionales, en combinación con los caminos en los árboles de expansión, pueden utilizarse para generar el grupo fundamental de la superficie. ^{[ 28 ]}

Cualquier fórmula de conteo que involucre vértices y caras, válida para todos los grafos planares, puede transformarse mediante la dualidad planar en una fórmula equivalente en la que se intercambian los roles de los vértices y las caras. La fórmula de Euler, que es autodual, es un ejemplo. Otro ejemplo, propuesto por Harary , involucra el lema del apretón de manos , según el cual la suma de los grados de los vértices de cualquier grafo es igual al doble del número de aristas. En su forma dual, este lema establece que en un grafo plano, la suma del número de lados de las caras del grafo es igual al doble del número de aristas. ^{[ 29 ]}

El grafo medial de un grafo plano es isomorfo al grafo medial de su dual. Dos grafos planares solo pueden tener grafos mediales isomorfos si son duales entre sí. ^{[ 30 ]}

Un grafo planar con cuatro o más vértices es maximal (no se pueden agregar más aristas manteniendo la planaridad) si y solo si su grafo dual es 3-conexo por vértices y 3-regular . ^{[ 31 ]}

Un grafo planar conexo es euleriano (tiene grado par en cada vértice) si y solo si su grafo dual es bipartito . ^{[ 32 ]} Un ciclo hamiltoniano en un grafo planar G corresponde a una partición de los vértices del grafo dual en dos subconjuntos (el interior y el exterior del ciclo) cuyos subgrafos inducidos son ambos árboles. En particular, la conjetura de Barnette sobre la hamiltonicidad de los grafos poliédricos bipartitos cúbicos es equivalente a la conjetura de que todo grafo planar maximal euleriano puede particionarse en dos árboles inducidos. ^{[ 33 ]}

Si un grafo planar G tiene un polinomio de Tutte T _G ( x , y ) , entonces el polinomio de Tutte de su grafo dual se obtiene intercambiando x e y . Por esta razón, si algún valor particular del polinomio de Tutte proporciona información sobre ciertos tipos de estructuras en G , entonces intercambiar los argumentos del polinomio de Tutte dará la información correspondiente para las estructuras duales. Por ejemplo, el número de orientaciones fuertes es T _G (0,2) y el número de orientaciones acíclicas es T _G (2,0) . ^{[ 34 ]} Para grafos planares sin puentes , las coloraciones de grafos con k colores corresponden a flujos nulos módulo k en el grafo dual. Por ejemplo, el teorema de los cuatro colores (la existencia de una 4-coloración para cada grafo planar) puede expresarse equivalentemente como afirmando que el dual de cada grafo planar sin puentes tiene un 4-flujo nulo. El número de k -coloraciones se cuenta (salvo un factor fácilmente calculable) mediante el valor del polinomio de Tutte T _G (1 − k ,0) y, dualmente, el número de k- flujos que no son cero en ningún lugar se cuenta mediante T _G (0,1 − k ) . ^{[ 35 ]} 

Un grafo st -planar es un grafo planar conexo con una orientación bipolar , la cual lo hace acíclico con una única fuente y un único sumidero, ambos ubicados en la misma cara. Este grafo puede transformarse en un grafo fuertemente conexo añadiendo una arista más, desde el sumidero hasta la fuente, a través de la cara exterior. El dual de este grafo planar aumentado es, a su vez, la ampliación de otro grafo st -planar. ^{[ 36 ]}

En un grafo plano dirigido , el grafo dual también puede hacerse dirigido, orientando cada arista dual con un giro de 90° en el sentido de las agujas del reloj desde la arista primal correspondiente. ^{[ 36 ]} Estrictamente hablando, esta construcción no es una dualidad de grafos planares dirigidos, porque partiendo de un grafo G y tomando el dual dos veces no se regresa a G mismo, sino que se construye un grafo isomorfo al grafo transpuesto de G , el grafo formado a partir de G invirtiendo todas sus aristas. Tomando el dual cuatro veces se regresa al grafo original.

El dual débil de un grafo plano es el subgrafo del grafo dual cuyos vértices corresponden a las caras acotadas del grafo primal. Un grafo plano es exterior-planar si y solo si su dual débil es un bosque . Para cualquier grafo plano G , sea G ⁺ el multigrafo plano formado al añadir un único vértice nuevo v en la cara no acotada de G y conectar v a cada vértice de la cara exterior (varias veces, si un vértice aparece varias veces en el límite de la cara exterior); entonces, G es el dual débil del dual (plano) de G ⁺ . ^{[ 37 ]}

El concepto de dualidad se aplica tanto a grafos infinitos incrustados en el plano como a grafos finitos. Sin embargo, es necesario tener cuidado para evitar complicaciones topológicas, como puntos del plano que no forman parte de una región abierta disjunta del grafo ni de una arista o vértice del mismo. Cuando todas las caras son regiones acotadas rodeadas por un ciclo del grafo, una incrustación de grafo planar infinito también puede considerarse como una teselación del plano, una cobertura del plano mediante discos cerrados (las teselas de la teselación) cuyos interiores (las caras de la incrustación) son discos abiertos disjuntos. La dualidad planar da lugar a la noción de teselación dual , una teselación formada al colocar un vértice en el centro de cada tesela y conectar los centros de las teselas adyacentes. ^{[ 38 ]}

El concepto de teselación dual también puede aplicarse a particiones del plano en un número finito de regiones. En este caso, está estrechamente relacionado con la dualidad de grafos planares, pero no es exactamente lo mismo. Por ejemplo, el diagrama de Voronoi de un conjunto finito de puntos es una partición del plano en polígonos, dentro de los cuales un punto está más cerca que cualquier otro. Los puntos en la envoltura convexa de la entrada dan lugar a polígonos de Voronoi no acotados, dos de cuyos lados son rayos infinitos en lugar de segmentos de línea finitos. El dual de este diagrama es la triangulación de Delaunay de la entrada, un grafo planar que conecta dos puntos mediante una arista siempre que exista un círculo que contenga esos dos puntos y ningún otro. Las aristas de la envoltura convexa de la entrada también son aristas de la triangulación de Delaunay, pero corresponden a rayos en lugar de segmentos de línea del diagrama de Voronoi. Esta dualidad entre diagramas de Voronoi y triangulaciones de Delaunay puede transformarse en una dualidad entre grafos finitos de dos maneras: añadiendo un vértice artificial en el infinito al diagrama de Voronoi, para que sirva como el otro extremo de todos sus rayos, ^{[ 39 ]} o tratando la parte acotada del diagrama de Voronoi como el dual débil de la triangulación de Delaunay. Aunque el diagrama de Voronoi y la triangulación de Delaunay son duales, su incrustación en el plano puede tener cruces adicionales más allá de los cruces de pares de aristas duales. Cada vértice del triángulo de Delaunay se sitúa dentro de su cara correspondiente del diagrama de Voronoi. Cada vértice del diagrama de Voronoi se sitúa en el circuncentro del triángulo correspondiente de la triangulación de Delaunay, pero este punto puede estar fuera de su triángulo.

K ₇ es dual al grafo de Heawood en el toro.

K ₆ es dual al gráfico de Petersen en el plano proyectivo.

El concepto de dualidad puede extenderse a incrustaciones de grafos en variedades bidimensionales distintas del plano. La definición es la misma: existe un vértice dual para cada componente conexa del complemento del grafo en la variedad, y una arista dual para cada arista del grafo que conecta los dos vértices duales a ambos lados de la arista. En la mayoría de las aplicaciones de este concepto, se restringe a incrustaciones con la propiedad de que cada cara es un disco topológico; esta restricción generaliza el requisito para grafos planares de que el grafo sea conexo. Con esta restricción, el dual de cualquier grafo incrustado en una superficie tiene una incrustación natural en la misma superficie, de modo que el dual del dual es isomorfo al grafo original y está incrustado isomórficamente en él. Por ejemplo, el grafo completo K ₇ es un grafo toroidal : no es planar, pero puede incrustarse en un toro, siendo cada cara de la incrustación un triángulo. Esta incrustación tiene como dual el grafo de Heawood . ^{[ 40 ]}

El mismo concepto funciona igualmente bien para superficies no orientables . Por ejemplo, K ₆ puede incrustarse en el plano proyectivo con diez caras triangulares como el hemi-icosaedro , cuyo dual es el grafo de Petersen incrustado como el hemi-dodecaedro . ^{[ 41 ]}

Incluso los grafos planares pueden tener incrustaciones no planares, con duales derivados de esas incrustaciones que difieren de sus duales planares. Por ejemplo, los cuatro polígonos de Petrie de un cubo (hexágonos formados al eliminar dos vértices opuestos del cubo) forman las caras hexagonales de una incrustación del cubo en un toro . El grafo dual de esta incrustación tiene cuatro vértices que forman un grafo completo K ₄ con aristas duplicadas. En la incrustación de toro de este grafo dual, las seis aristas incidentes a cada vértice, en orden cíclico alrededor de ese vértice, pasan dos veces por los otros tres vértices. A diferencia de la situación en el plano, esta incrustación del cubo y su dual no es única; el grafo del cubo tiene varias otras incrustaciones de toro, con diferentes duales. ^{[ 40 ]}

Muchas de las equivalencias entre las propiedades primarias y duales de los grafos planares no se generalizan a los duales no planares, o requieren un cuidado adicional en su generalización.

Otra operación sobre grafos incrustados en superficies es la dualidad de Petrie , que utiliza los polígonos de Petrie de la incrustación como caras de una nueva incrustación. A diferencia del grafo dual habitual, tiene los mismos vértices que el grafo original, pero generalmente se encuentra en una superficie diferente. ^{[ 42 ]} La dualidad de superficie y la dualidad de Petrie son dos de las seis operaciones de Wilson y, en conjunto, generan el grupo de estas operaciones. ^{[ 43 ]}

Un dual algebraico de un grafo conexo G es un grafo G ^* tal que G y G ^* tienen el mismo conjunto de aristas, cualquier ciclo de G es un corte de G ^* , y cualquier corte de G es un ciclo de G ^* . Todo grafo planar tiene un dual algebraico, que en general no es único (cualquier dual definido por una incrustación plana sirve). Lo contrario también es cierto, como lo estableció Hassler Whitney en el criterio de planaridad de Whitney : ^{[ 44 ]}

Un grafo conexo G es planar si y solo si tiene un dual algebraico.

El mismo hecho puede expresarse en la teoría de los matroides . Si M es el matroide gráfico de un grafo G , entonces un grafo G ^* es un dual algebraico de G si y solo si el matroide gráfico de G ^* es el matroide dual de M. Entonces, el criterio de planaridad de Whitney puede reformularse como que el matroide dual de un matroide gráfico M es a su vez un matroide gráfico si y solo si el grafo subyacente G de M es planar. Si G es planar, el matroide dual es el matroide gráfico del grafo dual de G. En particular, todos los grafos duales, para todas las diferentes incrustaciones planas de G , tienen matroides gráficos isomorfos. ^{[ 45 ]}

Para incrustaciones de superficies no planas, a diferencia de los duales planares, el grafo dual no es generalmente un dual algebraico del grafo primal. Y para un grafo no planar G , el matroide dual del matroide gráfico de G no es en sí mismo un matroide ^gráfico . Sin embargo, sigue siendo un matroide cuyos circuitos corresponden a los cortes en G , y en este sentido puede pensarse como un dual algebraico combinatoriamente generalizado de G. [ ^{46 ]} 

La dualidad entre grafos planares eulerianos y bipartitos puede extenderse a matroides binarios (que incluyen los matroides gráficos derivados de grafos planares): un matroide binario es euleriano si y solo si su matroide dual es bipartito . ^{[ 32 ]}

Los dos conceptos duales de circunferencia y conectividad de aristas se unifican en la teoría de matroides mediante la circunferencia del matroide : la circunferencia del matroide gráfico de un grafo planar es la misma que la circunferencia del grafo, y la circunferencia del matroide dual (el matroide gráfico del grafo dual) es la conectividad de aristas del grafo. ^{[ 19 ]}