PUMaC 2010 · 加试 · 第 2 题

Problem 2.2. ( ★★ , 6) Prove that 퐻 is a minor of 퐺 if and only if you can map each vertex 푣 ∈ 푉 ( 퐻 ) to a nonempty subset of 퐺 ’s vertices 푓 ( 푣 ) ⊂ 푉 ( 퐺 ) such that: ∙ For all 푣 ∈ 푉 ( 퐻 ), the subgraph of 퐺 induced on 푓 ( 푣 ) is connected. ∙ For all 푢, 푣 ∈ 푉 ( 퐻 ) with 푢 ∕ = 푣 , 푓 ( 푢 ) ∩ 푓 ( 푣 ) = {} . ∙ For all 푢, 푣 ∈ 푉 ( 퐻 ), ∣ 퐸 ( 푓 ( 푢 ) , 푓 ( 푣 )) ∣ − ∣ 푓 ( 푢 ) ∩ 푓 ( 푣 ) ∣ ≥ 퐸 ( { 푢 } , { 푣 } ) − ∣{ 푢 } ∩ { 푣 }∣ , where 퐸 ( 푋, 푌 ) is the number of edges with one endpoint in 푋 and the other in 푌 . Answer (sketch): First, we show that if 퐻 is a minor of 퐺 , the above holds, by induction on 푘 in the definition of minors. If 푘 = 0, 퐻 = 퐺 , and we can take 푓 ( 푣 ) = 푣 to satisfy the above. If not, then either 퐺 ∖ 푣 = 퐺 , or 퐺 ∖ 푒 = 퐺 , or 푘 푘 퐺/푒 = 퐺 , for some 퐺 satisfying the above and some 푣 or 푒 . In the first two 푘 푘 cases, the same 푓 as the inductive hypothesis gives for 퐺 works; in the third 푘 case, let 푓 map both vertices of 푒 to 푓 ( 푒 ). Second, we show that if the above holds, then 퐻 is a minor of 퐺 . For each 푣 ∈ 푉 ( 퐻 ), contract all the edges in the subgraph of 퐺 induced on 푓 ( 푣 ); this produces a single vertex since 푓 ( 푣 ) is connected, and for 푢 ∕ = 푣 , these vertices are distinct, since 푓 ( 푣 ) ∩ 푓 ( 푢 ) = {} . Delete any unused vertices and delete any edges between 푓 ( 푢 ) and 푓 ( 푣 ) in excess of the number of edges between 푢 and 푣 in 퐻 ; this gives 퐻 as a minor of 퐺 , as desired.