AbstractGeneralizing well‐known results of Erdős and Lovász, we show that every graph contains a spanning ‐partite subgraph with , where is the edge‐connectivity of . In particular, together with a well‐known result due to Nash‐Williams and Tutte, this implies that every 7‐edge‐connected graph contains a spanning bipartite graph whose edge set decomposes into two edge‐disjoint spanning trees. We show that this is best possible as it does not hold for infinitely many 6‐edge‐connected graphs. For directed graphs, it was shown by Bang‐Jensen et al. that there is no such that every ‐arc‐connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3‐partite subdigraph and that every strong semicomplete digraph on at least six vertices contains a spanning strong bipartite subdigraph. We generalize this result to higher connectivities by proving that, for every positive integer , every ‐arc‐connected digraph contains a spanning ()‐partite subdigraph which is ‐arc‐connected and this is best possible. A conjecture by Kreutzer et al. implies that every digraph of minimum out‐degree contains a spanning 3‐partite subdigraph with minimum out‐degree at least . We prove that the bound would be best possible by providing an infinite class of digraphs with minimum out‐degree which do not contain any spanning 3‐partite subdigraph in which all out‐degrees are at least . We also prove that every digraph of minimum semidegree at least contains a spanning 6‐partite subdigraph in which every vertex has in‐ and out‐degree at least .