The Higher-Order Edge Toughness of a Graph and Truncated Uniformly Dense Matroids

Abstract

In [Discrete Math. 111 (1993), 113-123], the $c$-th order edge toughness of a graph $G$ is defined as
$${\tau }_c(G)=\underset{\begin{array}{c}X\subseteq E(G),\mathrm{\&}\omega (G–X)>c\end{array}}{min}\left\{\frac{|X|}{\omega (G–X)–c}\right\},$$
for any $1\le c\le |V(G)|–1$. It is proved that ${\tau }_c(G)\ge k$ if and only if $G$ has $k$ edge-disjoint spanning forests with exactly $c$ components, and that for a given graph $G$ with $s=|E(G)|/(|V(G)|–c)$ and $1\le c\le |E(G)|$,
${\tau }_c(G)=s$ if and only if $|E(H)|\le s(|V(H)|–1)$ for any subgraph $H$ of $G$. In this note, we shall present short proofs of the abovementioned theorems and shall indicate that these results can be extended to matroids.