You are an expert at summarizing long articles. Proceed to summarize the following text: 
erds noticed @xcite that any graph @xmath3 with minimum degree @xmath4 at least @xmath5 contains a spanning , bipartite subgraph @xmath6 with @xmath7 . the proof for this fact is obtained by taking a maximal edge - cut , a partition of @xmath8 into two sets @xmath9 and @xmath10 , such that the number of edges with one endpoint in @xmath9 and one in @xmath10 , denoted @xmath11 , is maximal . observe that if some vertex @xmath12 in @xmath9 does not have degree at least @xmath1 in @xmath13 $ ] , then by moving @xmath12 to @xmath10 , one would increase @xmath11 , contrary to maximality . the same argument holds for vertices in @xmath10 . in fact this proves that for each vertex @xmath14 , by taking such a subgraph @xmath6 , the degree of @xmath12 in @xmath6 , denoted @xmath15 , is at least @xmath16 . this will be used throughout the paper . thomassen observed that the same proof shows the following stronger statement . given a graph @xmath3 which is at least @xmath17 _ edge - connected _ ( that is one must remove at least @xmath5 edges in order to disconnect the graph ) , then @xmath3 contains a bipartite subgraph @xmath6 for which @xmath6 is @xmath1 edge - connected . in fact , each edge - cut keeps at least half of its edges . this observation led thomassen to conjecture that a similar phenomena also holds for _ vertex - connectivity_.    before proceeding to the statement of thomassen s conjecture , we remind the reader that a graph @xmath3 is said to be @xmath1 _ vertex - connected _ or @xmath1-_connected _ if one must remove at least @xmath1 vertices from @xmath8 in order to disconnect the graph ( or to remain with one single vertex ) . we also let @xmath18 denote the minimum integer @xmath1 for which @xmath3 is @xmath1-connected . roughly speaking , thomassen conjectured that any graph with high enough connectivity also should contain a @xmath1-connected spanning , bipartite subgraph . the following appears as conjecture 7 in @xcite . [ conj7 ] for all @xmath1 , there exists a function @xmath0 such that for all graphs @xmath3 , if @xmath19 , then there exists a spanning , bipartite @xmath20 such that @xmath21 .    in this paper we prove that conjecture [ conj7 ] holds up to a @xmath2 factor by showing the following :    [ thm : graph ] for all @xmath1 and @xmath22 , and for every graph @xmath3 on @xmath22 vertices the following holds . if @xmath23 , then there exists a spanning , bipartite subgraph @xmath20 such that @xmath21 . because of the @xmath2 factor , we did not try to optimize the dependency on @xmath1 in theorem [ thm : graph ] . however , it looks like our proof could be modified to give slightly better bounds . in this section , we introduce a number of preliminary results . the first tool is the following useful theorem due to mader @xcite . [ mader ] every graph of average degree at least @xmath24 has an @xmath25-connected subgraph . because we are interested in finding bipartite subgraphs with high connectivity , the following corollary will be helpful . [ cor : maderbipartite ] every graph @xmath3 with average degree at least @xmath26 contains a ( not necessarily spanning ) bipartite subgraph @xmath6 which is at least @xmath25-connected . let @xmath3 be such a graph and let @xmath27 be a partition of @xmath8 such that @xmath11 is maximal . observe that @xmath28 , and therefore , the bipartite graph @xmath29 with parts @xmath9 and @xmath10 has average degree at least @xmath24 . now , by applying theorem [ mader ] to @xmath29 we obtain the desired subgraph @xmath6 . we will also make use of the following easy expansion lemma . [ lemma : joining two k connected graphs ] let @xmath30 and @xmath31 be two vertex - disjoint graphs , each of which is @xmath1-connected . let @xmath6 be a graph obtained by adding @xmath1 independent edges between these two graphs . then , @xmath32 . note first that by construction , one can not remove all the edges between @xmath30 and @xmath31 by deleting fewer than @xmath1 vertices . moreover , because @xmath30 and @xmath31 are both @xmath1-connected , each will remain connected after deleting less than @xmath1 vertices . from here , the proof follows easily . next we will show how to merge a collection of a few @xmath1-connected components and single vertices into one @xmath1-connected component . before stating the next lemma formally , we will need to introduce some notation . let @xmath33 be @xmath34 vertex - disjoint @xmath1-connected graphs , let @xmath35 be a set consisting of @xmath36 vertices which are disjoint to @xmath37 for @xmath38 , and let @xmath39 be a @xmath1-connected graph on the vertex set @xmath40 . also let @xmath41 be a @xmath42-tuple and @xmath43 denote the @xmath44th element of @xmath45 . finally , let @xmath46 denote the family consisting of all graphs @xmath3 which satisfy the following :    1 . the disjoint union of the elements of @xmath45 is a spanning subgraph of @xmath3 , and 2 .   for every distinct @xmath47 if @xmath48 , then there exists an edge in @xmath3 between @xmath43 and @xmath49 , and 3 .   for every @xmath50 , there is a set of @xmath1 independent edges between @xmath37 and @xmath1 distinct vertex sets @xmath51 , where @xmath52 . [ merge few into on ] let @xmath33 be @xmath34 vertex - disjoint graphs , each of which is @xmath1-connected , and let @xmath35 be a set of @xmath36 vertices for which @xmath53 for every @xmath54 . let @xmath39 be a @xmath1-connected graph on the vertex - set @xmath40 , and let @xmath55 . then , any graph @xmath56 is @xmath1-connected . let @xmath56 , and let @xmath57 be a subset of size at most @xmath58 . we wish to show that the graph @xmath59 is still connected . let @xmath60 be two distinct vertices in @xmath29 ; we show that there exists a path in @xmath29 connecting @xmath61 to @xmath62 . towards this end , we first note that if both @xmath61 and @xmath62 are in the same @xmath63 , then because each @xmath63 is @xmath1-connected , there is nothing to prove . moreover , if both @xmath61 and @xmath62 are in distinct elements of @xmath45 which are also disjoint from @xmath64 , then we are also finished , as follows . because @xmath39 is @xmath1-connected , if we delete all of the vertices in @xmath39 corresponding to elements of @xmath45 which intersect @xmath64 , the resulting graph is still connected . therefore , one can easily find a path between the elements containing @xmath61 and @xmath62 which goes only through `` untouched '' elements of @xmath45 , and hence , there exists a path connecting @xmath61 and @xmath62 . the remaining case to deal with is when @xmath61 and @xmath62 are in different elements of @xmath45 , and at least one of them is not disjoint with @xmath64 . assume @xmath61 is in some such @xmath43 ( @xmath62 will be treated similarly ) . using property @xmath65 of @xmath66 , there is at least one edge between @xmath43 and an untouched @xmath49 . therefore one can find a path between @xmath61 and some vertex @xmath67 in an untouched @xmath49 this takes us back to the previous case .      a _ directed graph _ or _ digraph _ is a set of vertices and a collection of directed edges ; note that bidirectional edges are allowed . for a directed graph @xmath68 and a vertex @xmath69 we let @xmath70 denote the out - degree of @xmath12 . we let @xmath71 denote the _ underlying graph of _ @xmath68 , that is the graph obtained by ignoring the directions in @xmath68 and merging multiple edges . in order to find the desired spanning , bipartite @xmath1-connected subgraph in theorem [ thm : graph ] , we look at sub - digraphs in an auxiliary digraph . the following is our main technical lemma and is the main reason why we have a @xmath2 factor . [ lem : main ] if @xmath68 is a finite digraph on at most @xmath22 vertices with minimum out - degree @xmath72 then there exists a sub - digraph @xmath73 such that    1 .   for all @xmath74 we have @xmath75 , and 2 . @xmath76 .    if @xmath77 , then there clearly is nothing to prove . so we may assume that @xmath78 . delete a separating set of size at most @xmath58 . the smallest component , say @xmath79 , has size at most @xmath80 and for any @xmath81 , every out - neighbor of @xmath12 is either in @xmath82 or in the separating set that we removed , and so @xmath83    we continue by repeatedly applying this step , and note that this process must terminate . otherwise , after at most @xmath2 steps we are left with a component which consists of one single vertex and yet contains at least one edge , a contradiction . with the preliminaries out of the way , we are now ready to prove theorem [ thm : graph ] . as long as @xmath63 contains a bipartite subgraph which is at least @xmath1-connected on at least @xmath86 vertices , let @xmath87 be such a subgraph of maximum size , and let @xmath88 . note that @xmath30 must exist as @xmath89 and so by corollary [ cor : maderbipartite ] , @xmath90 must contain a @xmath1-connected bipartite subgraph of size at least @xmath91 . let @xmath92 be the sequence obtained in this manner , and note that all the @xmath93 s are vertex disjoint with @xmath94 and @xmath95 . observe that if @xmath30 is spanning , then there is nothing to prove . therefore , suppose for a contradiction that @xmath30 is not spanning . let @xmath96 be the subset of @xmath8 remaining after this process ; note that it might be the case that @xmath97 . because each @xmath93 is a bipartite , @xmath1-connected subgraph of @xmath63 of maximum size and @xmath3 is @xmath98 connected , we show that the following are true :    1 .   for every @xmath99 , there are less than @xmath100 independent edges between @xmath93 and @xmath101 , and 2 .   for every @xmath102 and @xmath103 , the number of edges in @xmath3 between @xmath12 and @xmath93 , denoted by @xmath104 , is less than @xmath105 , and 3 .   for every @xmath106 , there exists a set @xmath107 consisting of exactly @xmath86 independent edges , each of which has exactly one endpoint in @xmath93 .    indeed , for showing @xmath108 , note that if there are at least @xmath100 independent edges between @xmath93 to @xmath101 , by pigeonhole principle , at least @xmath1 of them are between the same part of @xmath93 ( say @xmath109 ) and the same part of @xmath101 ( say @xmath110 ) therefore , the graph obtained by joining @xmath93 to @xmath101 with this set of at least @xmath1 edges is a @xmath1-connected ( by lemma [ lemma : joining two k connected graphs ] ) , bipartite graph and is larger than @xmath93 , contrary to the maximality of @xmath93 .    for showing @xmath111 , note that if there are at least @xmath105 between @xmath12 and @xmath93 then there are at least @xmath1 edges incident with @xmath12 touch the same part of @xmath93 , and let @xmath112 be a set of @xmath1 such edges . second , we mention that joining a vertex of degree at least @xmath1 to a @xmath1-connected graph trivially yields a @xmath1-connected graph . next , since all the edges in @xmath112 are touching the same part , the graph obtained by adding @xmath12 to @xmath113 and @xmath112 to @xmath114 , will also be bipartite . this contradicts the maximality of @xmath93 .    for @xmath115 , note first that since @xmath30 is not spanning , using @xmath111 we conclude that in the construction of the bipartite subgraphs @xmath92 in the process above , @xmath116 therefore , using corollary [ cor : maderbipartite ] , it follows that @xmath117 contains a bipartite subgraph of size at least @xmath91 which is also @xmath1-connected . therefore , the process does not terminate at this point , and @xmath31 exists ( that is , @xmath118 ) . it also follows that for each @xmath106 we have @xmath119 . next , note that @xmath3 is @xmath120 connected , and that each @xmath93 is of size at least @xmath121 . for each @xmath44 , consider the bipartite graph with parts @xmath113 and @xmath122 and with the edge - set consisting of all the edges of @xmath3 which touch both of these parts . using knig s theorem ( see @xcite , p. 112 ) , it follows that if there is no such @xmath107 of size @xmath86 , then there exists a set of strictly fewer than @xmath86 vertices that touch all the edges in this bipartite graph ( a vertex cover ) . by deleting these vertices , one can separate what is left from @xmath93 and its complement , contrary to the fact that @xmath3 is @xmath98 connected .    in order to complete the proof , we wish to reach a contradiction by showing that one can either merge few members of @xmath123 with vertices of @xmath124 into a @xmath1-connected component or find a @xmath1-connected component of size at least @xmath86 which is contained in @xmath124 . in order to do so , we define an auxiliary digraph , using a special subgraph @xmath125 , and use lemmas [ lem : main ] and [ merge few into on ] to achieve the desired contradiction . we first describe how to find @xmath29 . first , we partition @xmath124 into two sets , say @xmath9 and @xmath10 , where @xmath126 and observe that , using @xmath111 , since @xmath127 , any vertex @xmath128 must send edges to more than @xmath129 distinct elements in @xmath130 . for each @xmath131 , let @xmath107 be a set as described in @xmath115 . observe that , using @xmath111 , each such @xmath107 touches more than @xmath132 distinct elements of @xmath133 . let @xmath134 be a subset of size exactly @xmath135 such that each pair of edges in @xmath136 touches two distinct elements of @xmath133 , which of course are distinct from @xmath63 . recall that @xmath137 for every @xmath131 . let @xmath140 be mutually independent random variables . for each @xmath106 , if @xmath141 , then let @xmath142 and @xmath143 . otherwise , let @xmath144 and @xmath145 . for every @xmath146 , if @xmath147 , then let @xmath148 , and otherwise @xmath149 . now , delete all of the edges between two distinct elements of @xmath150 which receive the same label according to @xmath151 . finally , define @xmath29 as the spanning bipartite graph of @xmath3 obtained by deleting all of the edges within @xmath9 and for distinct @xmath44 and @xmath152 , the edges between @xmath93 and @xmath101 which are not contained in @xmath153 . recall by construction , using @xmath151 we generated labels at random ; therefore , by using chernoff bounds ( for instance see @xcite ) , one can easily check that with high probability the following hold :    1 .   for every @xmath106 , each set @xmath154 touches at least ( say ) @xmath155 other elements of @xmath45 , and 2 . for each @xmath156 , the degree of @xmath157 into @xmath158 is at least ( say ) @xmath159 , and 3 .   for each vertex @xmath160 , there exist edges between @xmath161 and @xmath162 that touch at least ( say ) @xmath163 distinct members of @xmath123 . now we are ready to define our auxiliary digraph @xmath68 . to this end , we first orient edges ( again , bidirectional edges are allowed , and un - oriented edges are considered as bidirectional ) of @xmath29 in the following way :    for every @xmath106 , we orient all of the edges in @xmath164 out of @xmath93 . we orient all of the edges between @xmath9 and @xmath162 out of @xmath9 . we orient edges between @xmath10 and @xmath162 arbitrarily , and we orient the remaining edges within @xmath158 in both directions . now , we define @xmath68 to be the digraph with vertex set @xmath165 , and @xmath166 if and only if there exists an edge between @xmath61 and @xmath62 in @xmath29 which is oriented from @xmath61 to @xmath62 .    in order to complete the proof , we first note that with high probability @xmath68 is a digraph on at most @xmath22 vertices with out - degree @xmath167 . this follows immediately from properties @xmath168-@xmath65 as well as the way we oriented the edges . therefore , one can apply lemma [ lem : main ] to find a sub - digraph @xmath169 such that      in fact , with high probability , @xmath170 note that by construction , every pair of edges which are oriented out of some @xmath93 must be independent and go to different components . using property @xmath171 above combined with the fact that @xmath172 , we may conclude that the subgraph @xmath173 induced by the union of all the components in @xmath174 satisfies @xmath175 . applying lemma [ merge few into on ] with @xmath176 and @xmath177 , it follows that @xmath178 . * case 1 : * @xmath179 contains @xmath113 for some @xmath44 . we note that this case is actually impossible because it would contradict the maximality of @xmath93 for the minimal index @xmath44 such that @xmath180 . * case 2 : * @xmath181 . we note that in this case , there must be at least one vertex @xmath182 . indeed , @xmath183 is @xmath1-connected , and there are no edges within @xmath9 . now , it follows from properties @xmath171  and @xmath184 above that @xmath185 thus , it follows that @xmath186 . combining this observation with the facts that @xmath183 is @xmath1-connected and @xmath181 , we obtain a contradiction . this case can not arise because @xmath183 should have been included as one of the bipartite subgraphs @xmath187 .      * acknowledgments . * the authors would like to thank the anonymous referees for valuable comments . the second author would also like to thank andrzej grzesik , hong liu and cory palmer for fruitful discussions in a previous attempt to attack this problem .
in 1989 , thomassen asked whether there is an integer - valued function @xmath0 such that every @xmath0-connected graph admits a spanning , bipartite @xmath1-connected subgraph . in this paper 
 we take a first , humble approach , showing the conjecture is true up to a @xmath2 factor .