Matroid connectivity

Matroid connectivity --- связность матроида.

For [math]\displaystyle{ X \subseteq E }[/math], the connectivity function, [math]\displaystyle{ \lambda }[/math], is defined by [math]\displaystyle{ \lambda(X) = r(X) + r(E - X) - r(M). }[/math]

Observe that [math]\displaystyle{ \lambda(X) = \lambda(E - X) }[/math]. For [math]\displaystyle{ j \geq 1 }[/math], a partition [math]\displaystyle{ (X,E-X) }[/math] of [math]\displaystyle{ E }[/math] is called a [math]\displaystyle{ j }[/math]-separation if [math]\displaystyle{ |X| \geq j }[/math], [math]\displaystyle{ |E-X| \geq j }[/math], and [math]\displaystyle{ \lambda(X) \leq j-1 }[/math]. When [math]\displaystyle{ \lambda(X) = j-1 }[/math], we call [math]\displaystyle{ (X,E-X) }[/math] an exact [math]\displaystyle{ j }[/math]-separation. For [math]\displaystyle{ k \geq 2 }[/math] we say matroid [math]\displaystyle{ M }[/math] is [math]\displaystyle{ k }[/math]-connected if [math]\displaystyle{ M }[/math] has no [math]\displaystyle{ j }[/math]-separation for [math]\displaystyle{ j \leq k-1 }[/math]. This definition of connectivity is refered to as Tutte [math]\displaystyle{ k }[/math]-connectivity to distinguish it from other types of [math]\displaystyle{ k }[/math]-connectivity. Tutte connectivity is invariant under duality. Moreover, from the definition it is clear that matroid connectivity begins with 2-connectivity. So when we say connected matroid we mean 2-connected matroid. The next two results compare matroid connectivity with graph connectivity.

Theorem 1. Let [math]\displaystyle{ G }[/math] be a graph with at least three vertices and no isolated vertex. Then [math]\displaystyle{ M(G) }[/math] is 2-connected if and only if [math]\displaystyle{ G }[/math] is 2-connected and has no loop.

Theorem 2. Let [math]\displaystyle{ G }[/math] be a graph with at least three vertices, no isolated vertex, and [math]\displaystyle{ G \not \approx K_{3} }[/math]. Then [math]\displaystyle{ M(G) }[/math] is 3-connected if and only if [math]\displaystyle{ G }[/math] is 3-connected and has no loop or parallel edges.