Processing graphs that carry temporal information (temporal graphs) has become increasingly important in real‑world applications. This paper investigates efficient solutions for temporal‑graph tasks by leveraging incremental Minimum Spanning Tree (MST) algorithms.\n\nThe first contribution systematically shows how a wide range of setting‑problem combinations in temporal‑graph processing can be solved using incremental MST, together with rigorous theoretical guarantees. Despite the problem’s significance, a gap exists between theory and practice: classic data structures such as the link‑cut tree offer strong asymptotic bounds but perform poorly on real data, while existing practical solutions lack non‑trivial theoretical assurances.\n\nThe second and main contribution introduces new incremental MST algorithms that are efficient both theoretically and empirically. We propose the AM‑tree data structure, which attains the same theoretical bound as the link‑cut tree for temporal‑graph processing while delivering superior practical performance. Experiments demonstrate that AM‑tree is competitive with or outperforms current practical solutions and is dramatically faster than the link‑cut tree—achieving 7.8‑11× speed‑ups on updates and 7.7‑13.7× on queries.\n\nExperimental setup includes synthetic benchmarks and real‑world temporal networks, measuring update latency, query latency, and overall throughput.\n\nConclusion: By reconciling optimal theoretical guarantees with strong empirical efficiency, AM‑tree provides a viable and high‑performance approach for incremental MST computation in temporal graphs.\n\nReview