= Solution
For a connected undirected weighted <graph>, a <spanning tree> connects all <vertices> without a <graph cycle>. A <minimum spanning tree> minimizes the sum of its <edge> weights. Disconnected input has no <spanning tree>, although the same methods produce a minimum spanning <forest>. Negative <edge> weights and ties cause no difficulty; a <tree> always contains exactly $|V|-1$ <edges>.
The central exchange argument is the <minimum spanning tree cut property>. Suppose a <forest> $F$ is contained in some <minimum spanning tree> $T$, and consider a cut with no <edge> of $F$ crossing it. Let $e$ be a lightest crossing <edge>. If $e\notin T$, adding it creates a <graph cycle>; the <graph path> in $T$ between its endpoints contains a crossing <edge> $f$. That $f$ is not in $F$, and $w(e)\leq w(f)$. Thus $T-f+e$ is another <spanning tree> with no larger weight and still contains $F$. It is also minimum and contains $F\cup\{e\}$. This proves that the chosen <edge> is safe, rather than merely asserting a greedy choice.
<Kruskal's algorithm> sorts all <edges> by increasing weight, starts with the empty <forest>, and adds an <edge> precisely when its endpoints are in different components. Each added <edge> is lightest across a component cut respected by the current <forest>. The exchange proof inductively keeps the <forest> inside a <minimum spanning tree>; connectedness makes the final <forest> a <spanning tree>, hence an optimum. Sorting takes $O(|E|\log|E|)$ comparisons, and even a simple component-merging implementation takes only polynomial additional work. Efficient component tracking improves that overhead further.
<Prim's algorithm> instead grows a single <tree>, repeatedly adding a lightest <edge> from its <vertex> set to the outside. The same cut argument proves correctness. A dense implementation using an array runs in $O(|V|^2)$ comparisons. The dual <minimum spanning tree cycle property> says a uniquely heaviest <edge> of a <graph cycle> belongs to no <minimum spanning tree>: exchanging it for a lighter crossing <edge> strictly improves any <tree> containing it. Ties must be handled carefully; a merely nonunique heaviest <edge> can occur in an optimum.
Complexity classes are formally classes of <decision problems>, so use the version asking whether a <graph> has a <spanning tree> of total weight at most a supplied threshold $K$. Assume <integer> or rational weights and threshold are encoded in binary. The input length includes all these bits, not only the numbers of <vertices> and <edges>. <P (complexity)> consists of <decision problems> decidable by a deterministic algorithm in time polynomial in that input length. <NP (complexity)> consists of those with polynomial-size <complexity certificates> verified in deterministic <polynomial time>, equivalently decidable in <polynomial time> by a nondeterministic machine.
Kruskal's algorithm constructs the optimum and compares its weight with $K$. Binary <integer> comparisons and sums are polynomial-time operations. Rational comparisons can be made by cross multiplication, and their summed numerator and denominator have polynomially bounded bit length: a product of input denominators has bit length no greater than the sum of their bit lengths. The combinatorial algorithm makes polynomially many such operations. Hence \b[the minimum-spanning-tree <decision problem> is in P]; the optimization version likewise has a polynomial-time algorithm.
For membership in NP, the <complexity certificate> is a list of $|V|-1$ selected <edges>. Check that every <edge> is present, that the <edges> connect all <vertices> and contain no <graph cycle>, and that their total weight is at most $K$. A <graph> search and binary arithmetic do this in <polynomial time>. A successful <complexity certificate> need not establish that its <tree> is minimum: it proves the threshold question's yes-answer. Conversely, a yes-instance has such a <tree> as a <complexity certificate>. Therefore
$$
\boxed{\text{the minimum-spanning-tree decision problem belongs to both P and NP}.}
$$
Membership in NP does not <arithmetic mean> NP-hardness; here the explicit greedy algorithm provides the stronger tractability result.
Back to article page
