グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。

グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。

1)長さ3の道を一つも含まない9個の頂点を持つグラフが持てる可能な最大の枝(辺)の数は何本か？またそのグラフをかけ。

2)7個の頂点を持つ連結グラフにおいて、すべての辺が少なくとも2つの閉路に含まれる最小の枝の数は何でしょうか。またそのグラフをかけ。

No.1 回答者： ありものがたり 回答日時： 2023/05/27 22:11

1)

長さ3の道を一つも含まないグラフの部分グラフは長さ3の道を一つも含まない。
よって、問題グラフから３頂点とそれに接続する辺を取り出した部分グラフは、
３頂点をもち、長さ3の道を一つも含まない。
そのようなものは、３頂点と２辺からなる直線状のグラフである。
この部分グラフに頂点を添加することを考える。
直線状のグラフの端点に辺とその先の頂点を添加すると
長さ3の道ができてしまうので、添加する辺は中央の頂点にしか接続できない。
できあがるグラフは、
中央の１頂点に他の８頂点が直接接続する星形のグラフである。

2)
「2つの閉路」どうしの関係について説明が無いが、
ともかく何らかの2つの閉路がありさえすれば良いのなら話は単純。
グラフが連結で全体として2つの閉路を持てば、
全ての頂点は2つ以上の閉路に含まれることになる。
７つの頂点を１つの閉路上に配置し、隣接しない１組の2点を辺で結べばよい。
その際、最小の辺数は８である。