Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Graph is Fun

Catupper
August 30, 2013
130

Graph is Fun

ぐらふつよい
JOIss2013グラフ理論班かつっぱ氏発表
辺彩色

Catupper

August 30, 2013
Tweet

Transcript

  1. 証明 • グラフの辺の数が n 未満の時に定理が成立してると仮定 • 辺の数が n のグラフ G

    についてひとつの辺 e を選ぶ – 最大次数はDとする • G – eはD色で辺彩色可能 • とりあえずG - eをD色でぬりわける