Enumerating necessary conditions

First, let us list the necessary conditions that the given graph is a path graph.

First, there must be \((N-1)\) edges by definition. But this condition alone give rise to the following graph:

You may realize that a vertex with three or more incident edges is illegal. What if we add another condition: “every vertex’s degree must be at most \(2\)?”

This is not enough, with the following graph being counterexample:

That is why we also have to add a connectivity condition. Thus we have the following three necessary conditions:

• There are exactly \((N-1)\) edges.
• Every vertex’s degree must be at most \(2\).
• The graph is connected.

In fact, this set is actually a sufficient condition too.

Confirming necessity

If a graph satisfies all of the three conditions above, there is exactly two vertices of degree \(1\). This is true because no vertex has a degree \(0\) (due to \(N \geq 2\) and connectivity) and thus the sum of degrees is twice as the number of edges, that is, \((2N-2)\).

Let \(s\) and \(t\) be the vertices of degree \(1\), If you start from \(s\) and repeat heading to an unvisited vertex, the following three holds:

• Due to the degree condition, there is always a unique destination except for when on vertex \(t\).
• Once you reach \(t\), there is no way to go.
• By the connectivity condition, you have visited entire vertices once you arrive \(t\).

When \(v_1, v_2, \dots, v_N\) are the visited vertices, there is always an edge between \(v_i\) and \(v_{i+1}\), and there is no edge between \(v_i\) and \(v_j\) if \(|i - j| \geq 2\). Thus, the graph is a path graph.

Therefore, the problem can be solved in a total of \(O(N + M)\) time. To determine connectivity, use DFS (Depth-First Earch), BFS (Breadth First Search), or Disjoint Set Union.

Sample code (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;
}