必要条件の列挙

与えられたグラフがパスグラフであるための必要条件を列挙していきます。

まず、定義より辺の本数は \(N-1\) 本でなければなりません。しかし、これだけでは以下のようなグラフも該当してしまいます。

この反例を見ると、\(3\) 本以上の辺が出ている頂点が存在してはならないことに気づくでしょう。そこで、「全ての頂点の次数が \(2\) 以下」という条件を加えてみます。

しかし、これだけでは正解することはできません。以下のようなグラフが反例となります。

よって、連結性も条件に加えなければなりません。これにより

• 辺がちょうど \(N-1\) 本
• 全ての頂点の次数が \(2\) 以下
• グラフが連結

という \(3\) つの必要条件が揃いましたが、実はこれが十分条件でもあることが示せます。

十分性の確認

グラフが前述の \(3\) つの条件を全て満たすとき、次数 \(1\) の頂点がちょうど \(2\) つ存在します。これは、(\(N \geq 2\) と連結性より) 次数 \(0\) の頂点が存在せず、次数の総和が辺の本数の \(2\) 倍、すなわち \(2N-2\) であることからわかります。

次数 \(1\) の頂点を \(s, t\) とします。\(s\) からスタートし、未訪問の頂点に移動することを繰り返すとき、以下の \(3\) つが成り立ちます。

• 次数の条件より、\(t\) 以外の頂点にいるとき、必ずちょうど \(1\) つの行き先が存在する
• \(t\) に到着した後はどこへも移動できない
• 連結性より、\(t\) に到着した時点で全ての頂点を訪問し終わっている

訪れた順番に頂点の番号を並べた列を \(v_1, v_2, \dots, v_N\) とおくと、\(v_i, v_{i+1}\) 間には必ず辺があり、\(|i - j| \geq 2\) のとき \(v_i, v_j\) を結ぶ辺は存在しません。よって、グラフがパスグラフであることが確認できました。

以上から、\(3\) つの条件をそれぞれ判定することで、この問題を \(O(N + M)\) で解くことができます。連結性の判定には、DFS や BFS、Union Find などを用いればよいです。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1;
        v -= 1;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    if (m != n - 1) {
        cout << "No\n";
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        if (graph[i].size() > 2) {
            cout << "No\n";
            return 0;
        }
    }
    vector<bool> reach(n);
    queue<int> que;
    reach[0] = true;
    que.push(0);
    while (not que.empty()) {
        const int u = que.front();
        que.pop();
        for (const int v : graph[u]) {
            if (not reach[v]) {
                reach[v] = true;
                que.push(v);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!reach[i]) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}