グラフ$G$とその全域木$B_1$と$B_2$に対して、$e$が$B_1$の辺ならば、 $B_2$の辺$f$で$(B_1\setminus\{e\})\union\{f\}$ (すなわち$B_1$の辺$e$を$f$で入れかえて得られるグラフ)も $G$の全域木になるようなものを見つけることができる。
実際$e$に接続する2頂点を$v$と$v'$とすると、$G$の頂点集合は、 $v$と$B_1\setminus\{e\}$の中の散歩道で結ぶことができる頂点の全体を$V$と、 $v'$と$B_1\setminus\{e\}$の中の散歩道で結ぶことができる頂点の全体 $V'$の素な和集合として表わされる。
$B_2$が全域木だから、頂点$v$と$v'$を結ぶ$B_2$の中の道が存在する。 この道の中には、$v\in V$、$v'\in V'$だから、 $V$に属する頂点と$V'$に属する頂点の両方に接続する辺が存在する。 そのひとつを$f$とする。
明かに$B_3:=(B_1\setminus\{e\})\union\{f\}$は、 その頂点集合が$V(G)$と一致する連結なグラフになる。
もし$B_3$が閉路$C$を含むならば、 $B_1$が(従って、$B_1\setminus\{e\}$も)閉路を含まないから、 $C$は辺$f$を含むはずである。 このとき$C\setminus\{f\}$は、 $V$の頂点と$V'$の頂点を結ぶ$B_1\setminus\{e\}$の中の道となり、 $V,\,V'$の取り方に矛盾する。
従って$B_3$は$G$の全域木である。
同様な結果がベクトル空間についても成り立つ。 $V$がベクトル空間で、$B_1$と$B_2$が$V$の基ならば、 $B_1$の任意の元$e$に対して、$(B_1\setminus\{e\})\union\{f\}$が $V$の基であるような$B_2$の元$f$が存在する。 この性質を抽象することにより、マトロイドの第一の定義を得る。
${\cal B}$の元を、$M$の基(base)と呼ぶ。 マトロイド$M$のどの基にも同じ個数の元が含まれている。 その個数のことを、$M$の階数(rank)と呼ぶ。
グラフ$G$に対して、$G$の辺集合と全域林の辺集合の全体からなるマトロイドを、 $G$の閉路マトロイド(circuit matroid)と呼び、$M(G)$と表わす。
また、ベクトル空間のベクトルの有限集合$E$と、$E$と同じ部分空間を張る $E$の一次独立な部分集合の全体からなるマトロイドを、 ベクトルマトロイド(vector matroid)と呼ぶ。
マトロイド$M=(E,{\cal B})$と$M'=(E',{\cal B}')$に対して、 全単射$f:E\rightarrow E'$で、
\[ A\in {\cal B}\iff f(A)\in {\cal B}'\ \forall A\subset E \]
をみたすものが存在するとき、$M$と$M'$は同型(isomorphic)であるという。
同型でないグラフから定義されたマトロイドが同型になることも有り得る。