11 _{専門}_{受験番号}

高知大学大学院理学研究科情報科学専攻（専門）

11 グラフ G に対してその線グラフ L(G) を次のように定める : (i) G の辺集合 E を L(G) の頂点集合とする。 (ii) e, f ∈ E が G で隣接するときに ef を L(G) の辺とする。線グラフに関する以下の問に答えよ。

(1) 頂点数 n のサイクル C_{n} の線グラフ L(C_{n}) を求めよ。

(2) 頂点数 4 の完全グラフ K_{4} の線グラフ L(K_{4}) を図示せよ。 (3) 連結なグラフ G の線グラフ L(G) は連結であることを示せ。