Re: [圖論]2題請教
※ 引述《nendi (midi)》之銘言：
: 1.Let G be a graph with mk edges.
: Prove that if G is k-edge colorable, then there is a k-edge coloring f of G
: in which every color class contains exactly m edges.
Let C_1,..,C_k be the color classes.
If |C_i|>|C_j|, consider C_i\cup C_j, there is a path P s.t.
|E(P)\cap C_i|=|E(P)\cap C_j|+1. Then we exchange the two colors on E(P) and
the following can be done by induction.
: 2.Prove that if a cubic graph G has a hamilton cycle,
: then G is 3-edge colorable.
cubic => n(G) is even
We can color the edges of the Hamiltonian cycle C by two colors, and color
E(G)-E(C) by another color.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.194.35
推
03/14 10:05, , 1F
03/14 10:05, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
圖論
1
1