この問題は、
「N頂点N辺の連結なグラフが与えられるので、頂点を2色に塗分けて、両端の頂点の色が異なるような辺の数を(最小/最大)化せよ(但し、色は2色とも1度は使用しなければならない)」
という問題です。
まず、最小は簡単で、これは1つの頂点を除いて全ての頂点を同じ色に塗ればよいので、最も隣接する頂点が少ない頂点を1つだけ異なる色にすればよく、具体的に両端の頂点の色が異なる辺の数をカウントするには、(自己辺や二重辺が存在しないので)辺の両端の頂点番号でバケットソートして最小をとればよいです。
次に、最大です。ここでは、N頂点N辺の連結なグラフであるということがミソです。N頂点N辺の連結なグラフ、ということは、これは木にちょうど1つ辺を加えたものです。
なぜなら、あるN頂点N辺のグラフから葉の部分を消し、そのグラフの葉の部分を消し…ということを繰り返すと必ず丁度1つの(、自己辺や二重辺がないため3頂点以上の)閉路ができ、ここからある1辺を消してもグラフはもちろん連結のままで、N頂点N-1辺のグラフは木となります。
これで、このグラフは木に1辺を加えたものだとわかりました。ここで、木は二部グラフなので解はN-1以上であることが確定して、最後にこのグラフそのものが二部グラフ(例えば、4頂点4辺の閉路)であれば解はN、そうでなければ解はN-1となります。
