公務員試験 H28年 国家一般職(電気・電子・情報) No.34解説

グラフにおいて各頂点に色をつけ，隣り合う2 頂点を互いに異なる色で塗ることを彩色といい，グラフを彩色するために必要な色の最小数をそのグラフの彩色数という。次の㋐～㋓のグラフのうち，彩色数が3 のもののみを挙げているのはどれか。

1．㋐，㋑
2．㋐，㋒
3．㋑，㋒
4．㋑，㋓
5．㋒，㋓

 

 

 

 

 

　解 説　　　　　

試してみると、㋒、㋓が３色で塗れます。試し方としては、下図のように、「１：まず１色を多くの点に結ばれている所＋おけるだけ置いてみる」→「２：残りをうまく塗れないか考えてみる」とすると、うまく塗れる通りを見つけやすいのではないかと思います。

以上より、正解は 5 です。