avewright/proofwiki-math huggingface dataset:
Theorem: Path in Tree is Unique

Let $T$ be a graph.
Then $T$ is a tree {{iff}} there is exactly one path between any two distinct vertices.

Proof:
=== Necessary Condition ===
{{:Path in Tree is Unique/Necessary Condition/Proof 1}}{{qed|lemma}}
Theorem: Path in Tree is Unique

Let $T$ be a graph.
Then $T$ is a tree {{iff}} there is exactly one path between any two distinct vertices.

Proof:
Let $T$ be a tree.
{{AimForCont}} there exists a pair of distinct vertices $u$ and $v$ in $T$ such that there is not exactly one path between them.
If there is no path between $u$ and $v$, $T$ is not connected.
In this case, $T$ is certainly not a tree.
So, in keeping with our supposition, there is more than one path between $u$ and $v$.
Let two of these paths be:
:$P_1 = \tuple {u, u_1, \ldots, u_i, r_1, r_2, \ldots, r_{j - 1}, r_j, u_{i + 1}, \ldots, v}$
:$P_2 = \tuple {u, u_1, \ldots, u_i, s_1, s_2, \ldots, s_{k - 1}, s_k, u_{i + 1}, \ldots, v}$
Now consider the path:
:$P_3 = \tuple {u_i, r_1, r_2, \ldots, r_{j - 1}, r_j, u_{i + 1}, s_k, s_{k - 1}, \ldots, s_2, s_1, u_i}$
It can be seen that $P_3$ is a circuit.
Thus by definition $T$ can not be a tree.
From Proof by Contradiction it follows that there is exactly one path between any pair of vertices.
Theorem: Path in Tree is Unique

Let $T$ be a graph.
Then $T$ is a tree {{iff}} there is exactly one path between any two distinct vertices.

Proof:
Let $T$ be such that between every pair of distinct vertices of $T$ there exists exactly one path.
Then {{apriori}} $T$ is connected.
Suppose $T$ had a circuit, say $\tuple {u, u_1, u_2, \ldots, u_n, v, u}$.
Then there are two paths from $u$ to $v$:
:$\tuple {u, u_1, u_2, \ldots, u_n, v}$
and
:$\tuple {u, v}$
Hence, by Modus Tollendo Tollens, $T$ can have no circuits.
That is, by definition, $T$ is a tree.
Theorem: Finite Connected Simple Graph is Tree iff Size is One Less than Order

Let $T$ be a finite connected simple graph of order $n$.
Then $T$ is a (finite) tree {{iff}} the size of $T$ is $n - 1$.

Proof:
By definition:
:the order of a (finite) tree is how many nodes it has
and:
:the size of a (finite) tree is how many edges it has.
Theorem: Finite Connected Simple Graph is Tree iff Size is One Less than Order

Let $T$ be a finite connected simple graph of order $n$.
Then $T$ is a (finite) tree {{iff}} the size of $T$ is $n - 1$.

Proof:
Let $T_{k + 1}$ be an arbitrary tree with $k + 1$ nodes.
Take any node $v$ of $T_{k + 1}$ of degree $1$.
Such a node exists from Finite Tree has Leaf Nodes.
Consider $T_k$, the subgraph of $T_{k + 1}$ created by removing $v$ and the edge connecting it to the rest of the tree.
By Connected Subgraph of Tree is Tree, $T_k$ is itself a tree.
The order of $T_k$ is $k$, and it has one less edge than $T_{k + 1}$ by definition.
We have {{hypothesis}} that $T_k$ has $k - 1$ edges.
So $T_{k + 1}$ must have $k$ edges.
Theorem: Finite Connected Simple Graph is Tree iff Size is One Less than Order

Let $T$ be a finite connected simple graph of order $n$.
Then $T$ is a (finite) tree {{iff}} the size of $T$ is $n - 1$.

Proof:
Let $T_{k + 1}$ be an arbitrary tree with $k + 1$ nodes.
Remove any edge $e$ of $T_{k + 1}$.
By definition of tree $T_{k + 1}$ has no circuits.
Therefore from Condition for Edge to be Bridge it follows that $e$ must be a bridge.
So removing $e$ disconnects $T_{k + 1}$ into two trees $T_1$ and $T_2$, with $k_1$ and $k_2$ nodes, where $k_1 + k_2 = k + 1$.
Then, {{hypothesis}}, $T_1$ and $T_2$ have $k_1 - 1$ and $k_2 - 1$ edges.
Putting the edge $e$ back again, it can be seen that $T_{k + 1}$ has $\paren {k_1 - 1} + \paren {k_2 - 1} + 1 = k$ edges.
Therefore a tree of order $k + 1$  is of size $k$.
Theorem: Connected Subgraph of Tree is Tree

Let $T$ be a tree.
Let $S$ be a subgraph of $T$ such that $S$ is connected.
Then $S$ is also a tree.

Proof:
Follows directly from the fact that by definition, $T$ has no circuits.
As $T$ has no circuits, then nor can $S$ have.
Hence $S$ is a connected simple graph with no circuits.
Thus by definition, $S$ is a tree.
{{qed}}
Category:Tree Theory
1hwn2ak43lszy2qs63d7p3rp9490j5z
Theorem: Finite Tree has Leaf Nodes

Every non-edgeless finite tree has at least two leaf nodes.

Proof:
Let the proposition we are proving in the case of a tree of order $k$ be denoted $\map P k$.
=== Basis for the Induction ===
That $\map P 2$ is true follows as the Unique Tree of Order 2 contains exactly two leaves (viz. its two nodes).
This is our basis for the induction.
=== Induction Hypothesis ===
Suppose $\map P i$ is true for all $i$ such that $2 \le i \le k$.
Then we need to demonstrated that $\map P i$ is true for all $i$ such that $2 \le i \le k + 1$.
This is our induction hypothesis.
=== Induction Step ===
This is our induction step:
Let $T_{k + 1}$ be a tree of order $k + 1$.
Pick an edge $e = \set {v_1, v_2}$ of $T_{k + 1}$.
Consider the subgraph $T_0$ obtained by removing $e$.
By Edge of Tree is Bridge, $e$ is a bridge and removing it results in a subgraph with two components.
By Connected Subgraph of Tree is Tree each such component is a tree.
Let $T_i$ be the component containing $v_i$.
Denote its order by $k_i$, where $i \in \set{1, 2}$
Since no nodes have been removed from $T_{k + 1}$, $k_1 + k_2 = k + 1$.
There are two cases:
==== Case 1 ====
'''Neither $T_1$ nor $T_2$ is of order $1$.'''
Then $2 \le k_i \le k - 1, i = 1, 2$.
By the induction hypothesis, both $T_1$ and $T_2$ have at least two leaves.
Either $v_1$ and $v_2$ are both leaves of the respective trees, or one of them is not.
Suppose that $v_1$ and $v_2$ are both leaves of the respective trees.
Then by adding $e$ back to the graph and thus recreating $T_{k + 1}$, $v_1$ and $v_2$ cease to be leaves.
However, at least one other leaf from each subgraph $T_i, i = 1, 2$ survives the addition, becoming a leaf of $T_{k + 1}$.
Therefore $T_{k + 1}$ has at least two leaves.
Suppose that either $v_1$ or $v_2$ is not a leaf of its respective tree.
Then $T_{k + 1}$ has at least three leaves.
{{qed|lemma}}
==== Case 2 ====
'''$T_1$ or $T_2$ is of order $1$.'''
{{WLOG}}, assume that $T_1$ is of order $1$, that is $k_1 = 1$.
This implies that $k_2 = k$.
Then, by the induction hypothesis, $T_2$ has at least two leaf nodes.
Also $k_1 = 1$ implies that $v_1$ is a leaf of $T_{k + 1}$.
Suppose that $v_2$ is one of the leaves of $T_2$.
Then by adding $e$ back and thus recreating $T_{k + 1}$, $v_2$ is no longer a leaf, though at least one other leaf of $T_2$ survives the addition, becoming a leaf of $T_{k + 1}$.
Therefore $T_{k + 1}$ has at least two leaves.
Suppose that $v_2$ is not one of the leaves of $T_2$.
Then $T_{k + 1}$ has at least three leaves.
{{qed|lemma}}
In both cases, the thesis follows by the Second Principle of Mathematical Induction.
{{qed}}
Theorem: Size of Cycle Graph equals Order

The size of a cycle graph equals its order.

Proof:
Follows immediately from:
:The fact that a cycle graph is $2$-regular
:The result Number of Edges of Regular Graph which says that an $r$-regular graph with $n$ vertices has $\dfrac {n r} 2$ edges.
{{qed}}
Category:Cycle Graphs
7spwmoa9qtdscb9urh7gmg5tejimxf5
Theorem: Path Graph from Cycle Graph

Removing one edge from a cycle graph leaves a path graph.

Proof:
Let $G_n$ be the graph obtained by removing any edge from the cycle graph $C_n$.
As each of those edges lies on a cycle, by Condition for Edge to be Bridge, none of them is a bridge.
So removing any edge from $C_n$ leaves the resulting subgraph of $C_n$ connected.
From Size of Cycle Graph equals Order, the cycle graph $C_n$ has $n$ edges.
So $G_n$ has $n$ vertices and $n - 1$ edges, and is connected.
From Finite Connected Simple Graph is Tree iff Size is One Less than Order, $G_n$ is a tree.
But $G_n$ has two vertices of degree $1$, and all the others are of degree $2$.
It follows that $G_n$ is traversable, and hence by definition is a path graph.
{{qed}}
Category:Cycle Graphs
Category:Path Graphs
f2ltugxtms9l0d8e20hs9m3omsrxk4o
Theorem: Cycle in Balanced Signed Graph

Let $G$ be a balanced signed graph.
Let $C$ be a cycle in $G$.
Then $C$ has an even number of negative edges.

Proof:
Let $G$ be a balanced signed graph.
Since $G$ is balanced, we can colour the vertices black and white, say, so that every edge has a black and a white end.
Consider any cycle $C$ in $G$.
As we proceed around $C$, there is a change of colour when we traverse a negative edge.
Since this is a cycle, the last colour is the same as the first one.
So there must be an even number of colour changes.
So there must be an even number of negative edges in $C$.
{{qed}}
Category:Cycles (Graph Theory)
Category:Balanced Signed Graphs
89trrii2ohnszrh0n3l3vcbkguntjxm
Theorem: Graph with Even Vertices Partitions into Cycles

Let $G = \struct {V, E}$ be a graph whose vertices are all even.
Then its edge set $E$ can be partitioned into cycles, no two of which share an edge.
The converse also holds: a graph which can be partitioned into cycles must have all its vertices even.

Proof:
Let $G = \struct {V, E}$ be a graph whose vertices are all even.
If there is more than one vertex in $G$, then each vertex must have degree greater than $0$.
Begin at any vertex $u$.
Since the graph is connected (if the graph is not connected then the argument will be applied to separate components), there must be an edge $\set {u, u_1}$ for some vertex $u_1 \ne u$.
Since $u_1$ has even degree greater than $0$, there is an edge $\set {u_1, u_2}$.
These two edges make a trail from $u$ to $u_2$.
Continue this trail, leaving each vertex on an edge that was not previously used, until we reach a vertex $v$ that we have met before.
(Note: $v$ may or may not be the same vertex as $u$. It does not matter either way.)
The edges of the trail between the two occurrences of $v$ must form a cycle.
Call the cycle formed by this process $C_1$.
If $C_1$ covers all the edges of $G$, the proof is complete.
Otherwise, remove the edges forming $C_1$ from the graph, leaving the graph $G_1$.
All the vertices in $G_1$ are still even.
So pick some vertex $u'$ in $G_1$.
Repeat the same process as before, starting with an edge $\set {u', u'_1}$.
By the same argument, we can generate a new cycle $C_2$, which has no edges in common with $C_1$.
If $C_2$ covers all the rest of the edges of $G$, then we are done.
Otherwise, remove the edges forming $C_2$ from the graph, leaving the graph $G_2$, which again contains only even vertices.
We continue in this way until we have used up all the edges of $G$.
By this time we have a number of cycles, $C_1, C_2, \ldots, C_k$ which between them contain all the edges of $G$ but no two of them have an edge in common.
{{qed}}
The converse is trivial:
All the vertices of a cycle by definition are  even.
So if we were to take all these cycles and add them to the graph in turn, each vertex would increase its order by an even number.
{{qed}}
Theorem: Condition for Bipartite Graph to be Hamiltonian

Let $G = \struct {A \mid B, E}$ be a bipartite graph.
Let $G$ be Hamiltonian.
Then $\card A = \card B$.
That is, there is the same number of vertices in $A$ as there are in $B$.

Proof:
Let $G = \struct {A \mid B, E}$ be a bipartite graph.
To be Hamiltonian, a graph $G$ needs to have a Hamilton cycle: that is, one which goes through all the vertices of $G$.
As each edge in $G$ connects a vertex in $A$ with a vertex in $B$, any cycle alternately passes through a vertex in $A$ then a vertex in $B$.
{{WLOG}}, suppose  that $\card A > \card B$, that is, that there are more vertices in $A$ than in $B$.
Let $\card A = m, \card B = n$.
Suppose $G$ has a Hamilton cycle $C$.
Let that cycle start at $u \in B$.
After $2 n$ edges have been traversed, we will have arrived back at $u$ again, and all the vertices of $B$ will have been visited.
But there will still be $m - n$ vertices in $A$ which have not been visited.
Hence $C$ can not be a Hamilton cycle.
{{qed}}
Theorem: Complete Hamiltonian Bipartite Graph

:$K_{m, n}$ is Hamiltonian {{iff}} $m = n > 1$.

Proof:
Clearly $K_{1, 1}$ is not Hamiltonian, although it does have a Hamiltonian path.
From Condition for Bipartite Graph to be Hamiltonian, if $m \ne n$ then $K_{m, n}$ is not Hamiltonian.
So let $m = n$.
We note that the degree of any vertex in $K_{n, n}$ is $n$.
Then we can use Ore's Theorem, and the result follows directly.
{{qed}}
Category:Hamiltonian Graphs
Category:Complete Bipartite Graphs
8gjk3t55lyupp69t2v7k7c5gg2yglxz
Theorem: Condition for Complete Bipartite Graph to be Semi-Hamiltonian

$K_{m, n}$ is semi-Hamiltonian {{iff}} either:
:$m = n = 1$
or:
:$m = n + 1$ (or $n = m + 1$).

Proof:
Let $K_{m, n}$ be a complete bipartite graph.
If $m = n = 1$ then $K_{m, n} = K_{1, 1}$ is trivially semi-Hamiltonian:
:100px
{{qed|lemma}}
If $m = n + 1$, we can construct a Hamiltonian path as follows.
Let $K_{m, n} = \struct {A \mid B, E}$ such that $\card A = m, A = \set {u_1, u_2, \ldots, u_m}, \card B = n, B = \set {v_1, v_2, \ldots, v_m}$.
We start at vertex $u_1 \in A$.
As $K_{m, n}$ is complete, there is an edge connecting $u_1$ to $v_1$.
From $v_1$, there is an edge connecting $v_1$ to $u_2$.
And so on.
There is therefore a Hamiltonian path $\tuple {u_1, v_1, u_2, v_2, \ldots, u_{n - 1}, v_{n - 1}, u_n, v_n, u_m}$ (where of course $u_m = u_{n + 1}$).
So when $m = n + 1$, $K_{m, n}$ has a Hamiltonian path.
However, from Condition for Bipartite Graph to be Hamiltonian, $K_{m, n}$ is only fully Hamiltonian if $m = n$.
Hence when $m = n + 1$, $K_{m, n}$ is semi-Hamiltonian.
Similarly, if $n = m + 1$ the same argument applies, but this time the Hamiltonian path is:
$\tuple {v_1, u_1, v_2, u_2, \ldots, v_{n - 1}, u_{n - 1}, v_m, u_m, v_n}$
where of course $v_n = u_{m + 1}$.
{{qed|lemma}}
Now, suppose $K_{m, n}$ is such that neither $m = n + 1$ nor $n = m + 1$, and it is not the case that $m = n = 1$.
If $m = n$, then from Complete Hamiltonian Bipartite Graph $K_{m, n}$ is Hamiltonian, and therefore not semi-Hamiltonian.
If $m > n + 1$, then we can once more trace a path $P$ through $K_{m, n} = \struct {A \mid B, E}$ as before.
However, at the end of $P$ there is a spare vertex in $A$ which has not been traversed which you can't get to without going back to one of the vertices in $B$ that you have already visited.
Similarly if $n > m + 1$.
{{qed|lemma}}
Hence the result.
{{qed}}
Category:Semi-Hamiltonian Graphs
Category:Complete Bipartite Graphs
tj2oxtxjkslfuxobjvqoyasnz9s9c2l
Theorem: Number of Components after Removal of Bridge

Let $G = \struct {V, E}$ be a graph.
Let $e \in E$ be a bridge.
Let $m$ be the number of components of $G$.
Then when $e$ is removed from $G$, the number of components in the remaining graph is $m + 1$.

Proof:
It is clear, by definition of a bridge, that removing $e$ increases the number of components.
So after $e$ is removed from $G$, the number of components in the remaining graph is at least $m + 1$.
Suppose that removing $e$ disconnects $G$ into more than $m + 1$ components.
Since $e$ joins only two vertices of $G$, it can link at most two of these components.
So there is at least one extra component when $e$ is put back into $G$.
So $G$ has more than $m$ components.
This contradicts the fact that $G$ has $m$ components.
Hence the result.
{{qed}}
Category:Graph Theory
mjbl7xvno5p63qzxk5diduoxqpfic7o
Theorem: Adding Edge to Tree Creates One Cycle

Adding a new edge to a tree can create no more than one cycle.

Proof:
From Equivalent Definitions for Finite Tree, adding an edge creates at least one cycle.
Suppose that adding an edge $\tuple {u, v}$ to a tree $T$ creates two or more cycles.
Let two such cycles be $\tuple {u, v, \ldots, u_1, u_2, \ldots, u}$ and $\tuple {u, v, \ldots, v_1, v_2, \ldots, u}$.
By removing the edge $\tuple {u, v}$ from this cycle, we have two paths from $v$ to $u$:
:$\tuple {v, \ldots, u_1, u_2, \ldots, u}$
:$\tuple {v, \ldots, v_1, v_2, \ldots, u}$.
But that means $T$ has more than one path between two nodes.
From Path in Tree is Unique, that means $T$ can not be a tree.
Hence the result.
{{qed}}
Category:Tree Theory
j5dlnos6q84vfpjzfbk0ro6e0nwl0op
Theorem: Number of Edges in Forest

Let $F = \struct {V, E}$ be a forest with $n$ nodes and $m$ components.
Then $F$ contains $n - m$ edges.

Proof:
By definition, a forest is a disconnected graph whose components are all trees.
Let the number of nodes in each component of $F$ be $n_1, n_2, \ldots, n_m$ where of course $\ds \sum_{i \mathop = 1}^m n_i = n$.
From Finite Connected Simple Graph is Tree iff Size is One Less than Order, the number of edges in tree $i$ is $n_i - 1$.
So the total number of edges in $F$ is:
{{begin-eqn}}
{{eqn | l = \sum_{i \mathop = 1}^m \paren {n_i - 1}
      | r = \sum_{i \mathop = 1}^m n_i - \sum_{i \mathop = 1}^m 1 
      | c = Summation is Linear
}}
{{eqn | r = n - m
      | c = Sum of Identical Terms
}}
{{end-eqn}}
{{qed}}
Theorem: Cayley's Formula

The number of distinct labeled trees with $n$ nodes is $n^{n - 2}$.

Proof:
{{MissingLinks}}
Follows directly from Bijection between Prüfer Sequences and Labeled Trees.
This shows that there is a bijection between the set of labeled trees with $n$ nodes and the set of all Prüfer sequences of the form:
:$\tuple {\mathbf a_1, \mathbf a_2, \ldots, \mathbf a_{n - 2} }$
where each of the $\mathbf a_i$'s is one of the integers $1, 2, \ldots, n$, allowing for repetition.
Since there are exactly $n$ possible values for each integer $\mathbf a_i$, the total number of such sequences is $\ds \prod_{i \mathop = 1}^{n - 2} n$.
The result follows from Equivalence of Mappings between Finite Sets of Same Cardinality.
{{qed}}
Theorem: Bijection between Prüfer Sequences and Labeled Trees

There is a one-to-one correspondence between Prüfer sequences and labeled trees.
That is, every labeled tree has a unique Prüfer sequence that defines it, and every Prüfer sequence defines just one labeled tree.

Proof:
Let $T$ be the set of all labeled trees of order $n$.
Let $P$ be the set of all Prüfer sequence of length $n-2$.
Let $\phi: T \to P$ be the mapping that maps each tree to its Prüfer sequence.
* From Prüfer Sequence from Labeled Tree, $\phi$ is clearly well-defined, as every element of $T$ maps uniquely to an element of $P$.
* However, from Labeled Tree from Prüfer Sequence, $\phi^{-1}: P \to T$ is also clearly well-defined, as every element of $P$ maps to a unique element of $T$.
Hence the result.
{{questionable|How is it immediate that the two constructions are mutually inverse?}}
{{qed}}
Category:Tree Theory
Category:Combinatorics
at1xa7kms9fqu084e9ql627g11avm6n
Theorem: Tree has Center or Bicenter

Every tree has either:
:$(1): \quad$ Exactly one center
or:
:$(2): \quad$ Exactly one bicenter,
but never both.
That is, every tree is either central or bicentral.

Proof:
A tree whose order is $1$ or $2$ is already trivially central or bicentral.
Let $T$ be a tree of order at least $3$.
First we establish that the construction of a center or bicenter actually works.
From Finite Tree has Leaf Nodes, there are always at least two nodes of degree $1$ to be removed.
By the Handshake Lemma, it is clear that $T$ must also have at least one node whose degree is greater than $1$: 
:$\ds \sum_{i \mathop = 1}^n \map {\deg_G} {v_i} = 2 q$
where $q$ is the number of edges in $T$.
But from Finite Connected Simple Graph is Tree iff Size is One Less than Order:
:$q = n - 1$
So if each node has degree $1$, then $n = 2 \paren {n - 1}$ and so $n = 2$.
Therefore if $n > 2$ there must be at least one node in $T$ of degree is greater than $1$.
Next, from Connected Subgraph of Tree is Tree, after having removed those nodes, what is left is still a tree.
Therefore the construction is valid. 
We need to show the following:
:$(1): \quad T$ has only one center or bicenter
:$(2): \quad T$ has either a center or a bicenter.
Suppose $T$ has more than one center or bicenter.
It would follow that at least one of the iterations constructing the center or bicenter disconnects $T$ into more than one component.
That could only happen if we were to remove an edge between two nodes of degree greater than $1$.
Hence $T$ has at most one center or bicenter.
Now to show that $T$ has at least one center or bicenter.
The proof works by the Principle of Complete Induction.
We know that a tree whose order is $1$ or $2$ is already trivially central or bicentral. This is our base case.
Suppose that all tree whose order is $n$ have at most one center or bicenter. This is our induction hypothesis.
Take a tree $T$ whose order is $n+1$ where $n > 2$.
Let $T$ have $k$ nodes of degree $1$.
We remove all these $k$ nodes.
This leaves us with a tree with $n + 1 - k$ nodes.
As we have seen that $T$ has at least one node whose degree is greater than $1$, $n + 1 - k \ge 1$.
As there are always at least two nodes of degree $1$, $n + 1 - k \le n - 1$.
So after the first iteration, we are left with a tree whose order is between $1$ and $n - 1$ inclusive.
By the induction hypothesis, this tree has either a center or bicenter.
The result follows by the Principle of Complete Induction.
{{qed}}
Category:Tree Theory
7gex675re6ggaos52iact6h57e9xgvc
Theorem: Sophie Germain's Identity

:$x^4 + 4 y^4 = \paren {x^2 + 2 y^2 + 2 x y} \paren {x^2 + 2 y^2 - 2 x y}$

Proof:
{{begin-eqn}}
{{eqn | o = 
      | r = \paren {x^2 + 2 y^2 + 2 x y} \paren {x^2 + 2 y^2 - 2 x y}
      | c = 
}}
{{eqn | r = x^4 + x^2 \cdot 2 y^2 - x^2 \cdot 2 x y + x^2 \cdot 2 y^2 + 4 y^2 - 2 y^2 \cdot 2 x y + x^2 \cdot 2 x y + 2 y^2 \cdot 2 x y - 2 x y \cdot 2 x y
      | c = 
}}
{{eqn | r = x^4 + 4 y^4
      | c = gathering up terms and cancelling
}}
{{end-eqn}}
{{qed}}
Theorem: Sophie Germain's Identity

:$x^4 + 4 y^4 = \paren {x^2 + 2 y^2 + 2 x y} \paren {x^2 + 2 y^2 - 2 x y}$

Proof:
{{begin-eqn}}
{{eqn | o = 
      | r = \paren {x^2 + 2 y^2 + 2 x y} \paren {x^2 + 2 y^2 - 2 x y}
      | c = 
}}
{{eqn | r = \paren {x^2 + 2 y^2}^2 - \paren {2 x y}^2
      | c = Difference of Two Squares
}}
{{eqn | r = x^4 + 2 \cdot x^2 \cdot 2 y^2 + 4 y^2 - 2 x y \cdot 2 x y
      | c = 
}}
{{eqn | r = x^4 + 4 y^4
      | c = gathering up terms and cancelling
}}
{{end-eqn}}
{{qed}}
Theorem: Prim's Algorithm produces Minimum Spanning Tree

Prim's Algorithm always produces a minimum spanning tree.

Proof:
Suppose that Prim's Algorithm produces a tree $T$.
Let there exist another spanning tree $S$ with a smaller total weight.
Let $e$ be an edge of smallest weight which lies in $T$ but not $S$.
If we add $e$ to $S$, we obtain a cycle, from Equivalent Definitions for Finite Tree.
This cycle contains an edge $e'$ which is in $S$ but not $T$, otherwise $T$ would not be a tree.
So, we replace $e'$ in $S$ with $e$ from $T$, and obtain a new spanning tree $S'$.
{{handwaving|This is just hiding the core of the argument in a sneaky sentence. E.g. in Prim's Algo, it may be that neither of the endpoints of $e'$ are in $T$ yet, so that it may not be added yet}}
From the method of construction of $T$, it follows that the weight of $e$ can not exceed that of $e'$.
So the total weight of $S'$ does not exceed the total weight of $T$.
Also, $S'$ has one more edge in common with $T$ than $S$ has.
We repeat the above procedure, and repeatedly change edges of $S$ for edges of $T$, and each time the weight of the intermediate graph does not exceed that of $T$.
Thus the weight of $T$ does not exceed that of $S$, contradicting the definition of $S$.
Hence $T$ must be a minimum spanning tree.
{{qed}}
Category:Prim's Algorithm
Category:Tree Theory
ozre8kd8wqp15erxzbps17hy4ow94xl