[圖論]兩題請教

[nendi (midi)]

1.Prove that an r-regular bipartite graph can be

partitioned into k-regular bipartite subgraphs if k is a factor of r.

這題給人感覺很簡單理所當然，但小弟卻不知道怎麼下手，

不知道有沒有大大可以指點一下方向呢?



2.Suppose there is a homomorphism of an n-vertex graph G to H

and H is vertex transitive.Prove that a(G)/│V(G)│大於等於 a(H)/│V(H)│



Ps.

a(G)為 maximum indpendent number


A homomorphis of a graph G to a graph H is a mapping f:V(G)->V(H) s.t.

f(x)f(y) \in E(H) whenever xy \in E(H)


A graph G is vertex-transitive if for every pair u,v \in V(G) there is

an automorphism that maps u to v.





感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.27.26.146
推 AstralBrain :第一題: 先證明k=1的時候是對的
→ AstralBrain :如果1對了 那我們只要隨便抓k個subgraph一組
→ AstralBrain :就可以湊出k-regular bipartite subgraph
→ AstralBrain :那k=1要怎麼證呢 其實就是證明regular bipartite
→ AstralBrain :graph有perfect matching.
→ AstralBrain :套用hall's theorem直接搞定
→ nendi       :原來這麼簡單啊~呵呵，謝謝樓上的幫忙