2部マトロイド

オイラーグラフは、すべての頂点の次数が偶数であるようなグラフだが、平面グラフにおいて2部グラフの双対はオイラーグラフとなる。Welsh (1969)は、これがマトロイドにも拡張できることを示した。つまり、2値マトロイドにおいて、2部マトロイドの双対はオイラーマトロイドとなる。

2値マトロイドでない場合、そうなるとは限らない。例えば、一様マトロイド ${\displaystyle U{}_{6}^{4}}$ は2部マトロイドではないが、この双対はオイラーマトロイドである。また、一様マトロイド ${\displaystyle U{}_{6}^{3}}$ は2部マトロイドであるが、オイラーマトロイドではない。

与えられた2値マトロイドが2部マトロイドかを多項式時間でテストすることが可能である^[2]。しかし、与えられたマトロイドがオイラーマトロイドであるかを、独立性オラクルを介してテストするには、指数回のオラクルアクセスを必要とする^[3]。