Wrath of Math · YouTube · 5:50
This 120-second whiteboard lesson introduces Kruskal's algorithm for finding a minimum spanning tree in a connected weighted graph. It first fixes notation: G is a connected weighted graph of order n, and T is the resulting minimum spanning tree. The narrator explains that a spanning tree on n vertices has n-1 edges, so the algorithm stops once that many edges are selected. The method is then written as four steps: choose a minimum-weight edge, choose another minimum-weight remaining edge, then repeatedly choose a minimum-weight remaining edge that does not form a cycle with the edges already selected, continuing until n-1 edges are obtained. In the last part, the video switches to a concrete five-vertex weighted example graph with vertices u, v, w, x, y, while reminding viewers that a spanning tree must contain all vertices of the original graph. The clip ends before the example is actually solved. This 120-second whiteboard clip demonstrates Kruskal's algorithm on a weighted graph with vertices u, v, w, x, y. The board lists four steps: choose a minimum-weight edge, choose another minimum-weight remaining edge, then keep choosing minimum-weight remaining edges that do not form cycles until n-1 edges are selected. The presenter applies the method in order, adding uv (weight 1), yx (weight 2), and wv (weight 3) to a duplicate vertex set on the right. He then explains that a spanning tree on 5 vertices needs edges. In the final step, two remaining edges both have weight 4, but uw is rejected because it would create a cycle, so ux is chosen instead. The clip ends just after that fourth edge is selected. This clip teaches Kruskal's algorithm for finding a minimum spanning tree in a connected weighted graph. It states the rule to keep selecting minimum-weight edges that do not form cycles until n-1 edges are chosen, defines the tree weight as the sum of edge weights, and works through two examples with answers 10 and 21. It also notes that tied edge weights can lead to different minimum spanning trees even though the minimum total weight is unique, and says the correctness proof is deferred to a later video.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The clip opens by stating the problem class: Kruskal's algorithm is used on a connected weighted graph to produce a minimum spanning tree. The board text and narration align on this setup, so the viewer first learns the input type and the desired output object.
Next the notation is fixed. Let be a connected weighted graph of order , meaning has vertices. The video then records a basic spanning-tree fact: a spanning tree on vertices has edges. This is not just background; it immediately determines the stopping rule for the algorithm.
With denoting the minimum spanning tree to be found, the procedure is written as four ordered steps. Step 1 says to select an edge of of minimum weight. The narration adds the tie-breaking detail that if several edges share the minimum weight, any one of them may be chosen as the first edge of the tree.
Step 2 continues the greedy process by selecting another remaining edge of minimum weight, which becomes the second edge of the spanning tree. At this stage the video has not yet imposed a cycle test, because with only one or two chosen edges the main issue is still just choosing cheap edges.
Step 3 introduces the essential restriction. Once two edges are already selected, any further edge might close a loop, and a tree cannot contain cycles. Therefore the algorithm now selects any remaining edge of minimum weight subject to the condition that it does not form a cycle with the previously selected edges. This is the central rule that distinguishes Kruskal's method from simply taking the cheapest edges indiscriminately.
Step 4 tells the viewer to repeat step 3 until edges have been selected. The connection back to the earlier fact is explicit: because a spanning tree on vertices has exactly edges, reaching that count means the construction is complete and the result is a minimum spanning tree.
The final portion turns from abstract procedure to a concrete example. A five-vertex weighted graph with labels appears on the left, while the same five vertices are shown isolated on the right as the place where the spanning tree will be assembled. The algorithm steps are pasted above for reference. Before starting the selection, the narrator reminds the viewer that a spanning tree must contain all vertices of the original graph, so the task is to choose edges of minimum total weight without omitting any vertex and without creating cycles. The clip ends here, before any edge is actually chosen in the example.
The clip opens on a black digital whiteboard with three zones: the algorithm text across the top, a weighted graph G on the left, and a duplicate set of vertices on the right for building the answer. The speaker explains that chosen edges will be highlighted on the left and then redrawn on the right, and that edge weights are the green numbers beside the edges.
Step 1 is applied first. Scanning all visible edge weights, the minimum is 1 on the edge between u and v. That edge is highlighted on the left and copied to the right-side tree, establishing the first edge of the spanning tree.
Step 2 asks for a remaining minimum-weight edge. The next smallest visible weight is 2 on the edge between y and x. The speaker notes that no cycle check is needed yet because two edges alone cannot form a cycle in this construction, so yx is added directly to the right-side tree.
Step 3 introduces the crucial restriction: among remaining edges, choose a minimum-weight edge only if it does not create a cycle with edges already selected. The edge wv of weight 3 satisfies this condition, so it is highlighted on the left and drawn on the right as the third tree edge.
The presenter then explains the stopping rule written as step 4. A spanning tree on n vertices is complete once n-1 edges have been selected. Since this graph has 5 vertices, the target count is , and the board shows that three edges are already present, so exactly one more edge is needed.
For the fourth edge, the remaining minimum weight is 4, shared by two candidate edges. The edge uw is rejected because adding it would close a cycle with the already chosen edges. The only valid minimum-weight choice is therefore ux, which is selected and added to the right-side tree. The clip ends immediately after this fourth edge is chosen.
The clip opens on the tail end of a worked example. The on-screen algorithm says to repeat the cycle-avoiding selection step until n-1 edges have been chosen, and the narrator immediately applies that rule to a 5-vertex graph: since , the algorithm stops after edges, and the selected edges form a minimum spanning tree.
The next concept is the weight of the resulting tree. Calling the tree T, the video defines as the sum of the weights of the edges in T. For the displayed tree, the edge weights are 2, 4, 1, and 3, so the calculation is .
The narrator then emphasizes the minimality property: the graph has many spanning trees, but none has total weight below 10. This is presented as the key payoff of Kruskal's algorithm in the example.
A second graph is introduced as a practice problem. The same algorithm is to be applied: keep choosing minimum-weight remaining edges that do not create a cycle until the tree is complete.
For this second example, the video states that the minimum spanning tree weight is 21. The narrator adds that the viewer's answer should match because the minimum total weight is unique, even if the tree shape need not always be unique.
The clip then clarifies a subtle point about uniqueness. When several edges are tied for minimum weight, Kruskal's algorithm may require an arbitrary choice, so different minimum spanning trees can result from the same graph. The narrator says this particular second graph does not create that issue, so the displayed tree is the expected one.
The final instructional segment restates the method formally: for a connected weighted graph G of order n, Kruskal's algorithm selects a minimum-weight edge, then another minimum-weight remaining edge, then continues selecting minimum-weight remaining edges that do not form cycles with previously chosen edges, repeating until n-1 edges have been selected.
The closing remarks say that the correctness proof is postponed to a later video and mention Prim's algorithm as another, slightly more complicated method for finding minimum spanning trees. After that, the mathematics ends and the clip moves into outro music and end-card visuals.
The video states that Kruskal's algorithm finds a minimum spanning tree in a connected weighted graph. Thus the input is not an arbitrary graph but one that is both connected and equipped with edge weights, and the output is a spanning tree of minimum total weight.
If a graph has order , meaning vertices, then any spanning tree of that graph contains exactly edges. The video uses this fact to justify the stopping condition in Kruskal's algorithm.
The first step is to select an edge of the graph with minimum weight. If several edges tie for minimum weight, the video says to choose any one of them; that chosen edge becomes the first edge of the spanning tree.
After the first edge is chosen, the algorithm selects another edge of minimum weight from the remaining edges. This becomes the second edge of the spanning tree.
From the third edge onward, the algorithm chooses a remaining edge of minimum weight subject to the condition that adding it does not form a cycle with the edges already selected. The video explains this by noting that trees cannot have cycles.
The algorithm repeats the cycle-avoiding minimum-weight selection until exactly edges have been chosen. At that point the selected edges form a minimum spanning tree.
Before the worked example begins, the video explicitly reminds the viewer that a spanning tree by definition contains all vertices of the original graph. Therefore Kruskal's algorithm is not choosing a subset of vertices; it is choosing a subset of edges that connects all vertices with minimum total weight and no cycles.
The clip introduces a concrete example graph with vertices and visible edge weights including , , , , , , , , , and . The same five vertices are also drawn isolated on the right as the future location of the spanning tree. The algorithm steps are pasted above the example. No edge selection is completed before the clip ends.
The video states the method in four steps: select a minimum-weight edge of G; select a remaining minimum-weight edge; then repeatedly select a remaining minimum-weight edge that does not form a cycle with previously selected edges; stop when n-1 edges have been chosen. This is the procedural backbone of the whole clip.
After the first edge is chosen, the speaker explicitly says the second minimum-weight edge can be taken directly because it is impossible to create a cycle with just two edges. This distinguishes step 2 from step 3, where the no-cycle condition becomes necessary.
From the third edge onward, the algorithm only accepts a minimum-weight remaining edge if it does not create a cycle with the edges already in the tree. In the example, wv of weight 3 is accepted because it connects a new vertex without closing a loop.
The clip uses the fact that a spanning tree on n vertices has n-1 edges. Here the graph has 5 vertices, so the algorithm must stop after 4 edges. The board makes this concrete with the written calculation .
When two remaining edges both have minimum weight 4, the algorithm does not choose arbitrarily. The edge uw is rejected because it would form a cycle, while ux is accepted. This card captures the central decision rule in the last part of the clip.
Running the algorithm on the displayed graph produces the edge set {uv, yx, wv, ux}. These are exactly the edges drawn on the duplicated vertex set at the right by the end of the segment.
For a connected weighted graph G of order n, Kruskal's algorithm builds a minimum spanning tree by repeatedly choosing a remaining edge of minimum weight that does not create a cycle with the edges already chosen. The process stops once n-1 edges have been selected.
A spanning tree on n vertices has exactly n-1 edges. The video uses this fact directly in the first example: with 5 vertices, it computes and stops after four selected edges.
If T is the spanning tree produced by the algorithm, its weight is the sum of the weights of all edges in T. In the first example, the displayed tree has edge weights 2, 4, 1, and 3, so .
Applying Kruskal's algorithm to the first 5-vertex graph yields a tree with four edges. The narrator states that although the graph has many spanning trees, none has weight less than 10, so the computed tree is minimum.
The video presents a larger 6-vertex graph as practice. After applying the same algorithm, the narrator gives the minimum spanning tree weight as 21 and says the viewer's total should match because the minimum weight itself is unique.
The clip distinguishes two ideas. The minimum total weight is unique, but the actual tree need not be unique if there are ties among minimum-weight edges. In such cases Kruskal's algorithm may require an arbitrary choice, producing different valid minimum spanning trees from the same graph.
This segment explains and illustrates Kruskal's algorithm but does not prove its correctness. The narrator explicitly says a later video will prove that the algorithm works, and also mentions Prim's algorithm as a different method for minimum spanning trees.
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
The board states "Let G be a connected weighted graph of order n."
The narrator says, "Let G be a connected weighted graph of order n."
G
A connected weighted graph on which Kruskal's algorithm is run.
connected weighted graph
The board uses "order n" in the setup sentence.
The narrator explains that this means the graph has n vertices.
n
The order of the graph, i.e. the number of vertices.
positive integer vertex count
The board states "Kruskal's Algorithm finds a minimum spanning tree T in the following manner."
The narrator says the algorithm finds a minimum spanning tree, say T.
T
The minimum spanning tree produced by Kruskal's algorithm.
subgraph of G
The narrator says a spanning tree of a graph with n vertices will have n minus 1 edges.
Step 4 on the board reads "Repeat 3. until n-1 edges have been selected".
n-1
The number of edges in any spanning tree of an n-vertex graph, and therefore the stopping count for the algorithm.
integer edge count
The worked example graph shows five labeled vertices u, v, w, x, y.
The narrator introduces "this graph here" as the example for running the algorithm.
u, v, w, x, y
Vertex labels in the example graph used to demonstrate Kruskal's algorithm.
vertices of the example graph
The written algorithm repeatedly refers to edges of G.
The speaker says to select an edge of G of minimum weight.
G
the weighted graph on which Kruskal's algorithm is being demonstrated
weighted undirected graph with vertices u, v, w, x, y
The left graph and the duplicated right-side vertex set are labeled u, v, w, x, y.
The speaker names edges joining u and v, y and x, w and v, u and w, and u and x.
u, v, w, x, y
the five vertices of the example graph
vertex set of G
Step 4 is written as Repeat 3 until n-1 edges have been selected.
The speaker explains that n is the number of vertices of the graph.
n
the number of vertices in the graph
positive integer; here
Green numbers are placed next to edges in the left graph.
The speaker says the weight of each edge is written next to it in green.
edge weight
numeric cost assigned to each edge, used to choose minimum-weight edges
visible values include 1, 2, 3, 4, 5, 6, 7
The written algorithm text repeatedly uses G in phrases such as "Select an edge of G" and later "Let G be a connected weighted graph of order n."
G
A connected weighted graph to which Kruskal's algorithm is applied.
connected weighted graph
The algorithm text says "Repeat 3. until n-1 edges have been selected".
At 67.5 s the screen states "Let G be a connected weighted graph of order n."
n
The order of G, i.e. the number of vertices in the graph.
positive integer
The narrator says, "If we call this tree T, then W of T, the weight of the spanning tree, is equal to 10."
The screen shows for the first worked example and later for the second worked example.
T
The minimum spanning tree produced by Kruskal's algorithm in the worked examples.
tree subgraph of G
Top text reads "Kruskal's Algorithm finds a minimum spanning tree in a connected weighted graph."
The narrator repeats that Kruskal's algorithm finds a minimum spanning tree in a connected weighted graph.
The video defines the setting for Kruskal's algorithm as a connected weighted graph, and states that the algorithm's output is a minimum spanning tree for that graph.
The input graph is connected.
The input graph is weighted.
The desired output is a minimum spanning tree.
The narrator says a spanning tree of a graph with n vertices will have n minus 1 edges.
Later step 4 explicitly uses "until n-1 edges have been selected".
For a graph of order n, any spanning tree contains exactly n-1 edges. The video uses this fact to justify when Kruskal's algorithm can stop.
T is a spanning tree of a graph with n vertices.
The narrator says, "Remember that a spanning tree by definition contains all the vertices of the original graph."
Before applying the algorithm to the example, the video reminds the viewer that a spanning tree includes every vertex of the original graph; the algorithm only chooses which edges to keep so that total weight is minimized.
The chosen subgraph is a spanning tree of the original graph.
Step 1 on the board reads "Select an edge of G of minimum weight".
The narrator explains that if several edges tie for minimum weight, one of them is selected as the first edge of the spanning tree.
The first step of Kruskal's algorithm is to select an edge of the graph with minimum weight. If multiple edges share that minimum weight, any one of them may be chosen as the first edge of the spanning tree.
Work in a connected weighted graph G.
Choose an edge attaining the minimum weight among all edges of G.
Step 2 on the board reads "Select a remaining edge of G of minimum weight".
The narrator says to select another remaining edge of minimum weight as the second edge of the spanning tree.
After the first edge is chosen, the algorithm selects from the remaining edges another edge of minimum weight. This becomes the second edge of the spanning tree.
One edge has already been selected.
Choose a minimum-weight edge among the edges not yet selected.
Step 3 on the board reads "Select any remaining edge of G of minimum weight that does not form a cycle with the previously selected edges".
The narrator explains that once two edges are present, any additional edge could create a cycle, and trees cannot have cycles.
From the third edge onward, the algorithm repeatedly chooses a remaining edge of minimum weight subject to the condition that adding it does not create a cycle with the edges already selected. The cycle restriction is justified because a tree cannot contain cycles.
At least two edges have already been selected.
Among remaining edges, choose one of minimum weight that does not complete a cycle with the current selected set.
Step 4 on the board reads "Repeat 3. until n-1 edges have been selected".
The narrator says to repeat step 3 until n minus 1 edges have been selected, yielding a minimum spanning tree.
The final procedural instruction is to keep repeating the cycle-avoiding minimum-weight selection until the algorithm has accumulated n-1 edges. At that point the selected edges form a minimum spanning tree.
Continue applying step 3.
Stop when exactly n-1 edges have been selected.
The board lists four steps: 1. Select an edge of G of minimum weight. 2. Select a remaining edge of G of minimum weight. 3. Select any remaining edge of G of minimum weight that does not form a cycle with the previously selected edges. 4. Repeat 3 until n-1 edges have been selected.
The speaker reads and applies these steps in order while constructing the spanning tree.
The clip presents Kruskal's algorithm as a greedy edge-selection method. First take a globally minimum-weight edge, then take another minimum-weight edge from the remainder, then continue choosing minimum-weight remaining edges only if they do not create a cycle with already chosen edges, repeating until n-1 edges are selected.
The graph G is weighted.
Edges are considered in nondecreasing weight order among remaining candidates.
A candidate edge is rejected if it forms a cycle with previously selected edges.
The process stops after n-1 edges have been selected.
Step 4 explicitly states n-1 edges.
The speaker says one less edge than we have vertices because at that point we will have completed our spanning tree.
The speaker writes for this example.
The video uses the fact that once n-1 edges have been selected without forming cycles, the spanning tree is complete. For the displayed graph with five vertices, this means exactly four edges are needed.
The selected edges form a spanning tree of a graph with n vertices.
In this example , so the target number of edges is 4.
The screen lists step 4: "Repeat 3. until n-1 edges have been selected".
The narrator says, "Have n minus one or four edges, we can stop and we have a minimum spanning tree."
Kruskal's algorithm stops once n-1 edges have been selected; at that point the chosen edges form a minimum spanning tree of the connected weighted graph.
G is a connected weighted graph
n is the number of vertices of G
The narrator says, "If we call this tree T, then W of T, the weight of the spanning tree, is equal to 10. That's just the sum of the weights of the edges, 2 plus 4 plus 1 plus 3."
The screen writes next to the extracted tree.
The weight of a spanning tree T is the sum of the weights of all edges belonging to T. In the first example, the displayed tree has edge weights 2, 4, 1, and 3, so its total weight is 10.
T is a spanning tree of a weighted graph
denotes the weight of edge e
The screen shows the full algorithm text: "Kruskal's Algorithm finds a minimum spanning tree in a connected weighted graph. Let G be a connected weighted graph of order n. Kruskal's Algorithm finds a minimum spanning tree T in the following manner. 1. Select an edge of G of minimum weight 2. Select a remaining edge of G of minimum weight 3. Select any remaining edge of G of minimum weight that does not form a cycle with the previously selected edges 4. Repeat 3. until n-1 edges have been selected".
The narrator summarizes, "So that's Kruskal's algorithm for finding a minimum spanning tree."
Kruskal's algorithm constructs a minimum spanning tree by repeatedly choosing a remaining edge of minimum weight that does not create a cycle with the edges already chosen, continuing until n-1 edges have been selected.
G is a connected weighted graph
n is the order of G
The narrator states that a spanning tree of a graph with n vertices will have n minus 1 edges, so the algorithm can stop once n minus 1 edges have been selected.
The later written step 4 uses the same stopping criterion.
In a graph of order n, Kruskal's algorithm can stop once n-1 edges have been selected because a spanning tree on n vertices has exactly n-1 edges.
The graph has n vertices.
The selected edges are intended to form a spanning tree.
For a connected weighted graph of order n.
The speaker says that at this point we can select any edge of minimum weight because it's impossible that we'll create a cycle with just two edges.
After selecting the first edge, the second minimum-weight edge can be chosen without checking for a cycle because two edges alone cannot create a cycle in the presented construction.
Only two edges have been selected so far.
The graph is treated as a simple undirected graph in the demonstration.
for the current stage of the example after step 1 and before step 3
Step 4 on the board says Repeat 3 until n-1 edges have been selected.
The speaker explains that this is when the spanning tree is completed.
The algorithm repeats the cycle-avoiding selection step until n-1 edges have been selected, at which point the spanning tree is complete.
n is the number of vertices of the graph.
Selected edges have been chosen by the stated minimum-weight, no-cycle rule.
for the graph G in the example and for the general procedure written on the board
The narrator says the tree weight is 10 and explains it as .
The screen writes .
For the first displayed 5-vertex weighted graph, the tree extracted by Kruskal's algorithm has total weight , and no spanning tree of that graph has smaller weight.
The graph shown on the left is the input graph
The right-hand tree is the output of Kruskal's algorithm
Edge weights are those labeled on the diagram
For the specific graph shown in the first example.
The narrator asks, "What's the weight of your tree? The weight of mine is 21, and of course that should be the weight of yours because there's only one minimum weight."
The screen writes .
For the second displayed 6-vertex weighted graph, the minimum spanning tree found by Kruskal's algorithm has total weight .
The graph shown is the second worked example
The algorithm is applied as stated on screen
For the specific graph shown in the second example.
The narrator says, "Remember that this algorithm can produce different minimum spanning trees from the same graph since at times it is necessary to make an arbitrary choice among edges that are tied for the minimum weight. However, you won't encounter such a thing with this graph, so your minimum spanning tree should look like this."
Kruskal's algorithm may produce different minimum spanning trees from the same graph when there are ties among minimum-weight candidate edges, but the second example graph has no such tie issue, so the resulting tree is uniquely determined up to the displayed structure.
The graph is weighted
Edges may have equal minimum weights during selection
There exist weighted graphs for which different valid tie choices lead to different minimum spanning trees; for the second example graph shown, the video states this situation does not arise.
The narrator says, "In a later video, we'll actually prove that the algorithm works, so we can be 100% sure it does what it's supposed to."
The video does not prove Kruskal's algorithm here; it states that a later video will prove that the algorithm works.
This clip is part of a series
For the algorithm presented in this clip.
The narrator says that after two edges are selected, any additional edge could possibly create a cycle, and trees cannot have cycles.
Step 3 is written as selecting a remaining minimum-weight edge that does not form a cycle with previously selected edges.
The algorithm first selects one minimum-weight edge and then a second minimum-weight remaining edge.
These are steps 1 and 2 as written on the board and spoken aloud.
Once two edges are already chosen, a third edge might close a loop with them.
This is the narrator's stated reason for introducing a new restriction after the first two selections.
Because a tree cannot contain cycles, the algorithm must reject any candidate edge that would create one.
This follows from the definition of a tree and is explicitly invoked in the narration.
Therefore step 3 adds the rule that each subsequent minimum-weight edge is accepted only if it does not form a cycle with the previously selected edges.
The speaker narrates each choice: edge uv of weight 1, edge yx of weight 2, edge wv of weight 3, rejects uw of weight 4 because it would create a cycle, and selects ux of weight 4.
The right-side duplicated vertices accumulate the chosen edges in the same order.
The board shows the stopping count .
Apply step 1 by scanning all edges and choosing the minimum-weight edge.
The board states: Select an edge of G of minimum weight.
The chosen first edge is the edge joining u and v with weight 1, and it is added to the spanning tree on the right.
This is the smallest visible edge weight in the graph.
Apply step 2 by choosing a remaining minimum-weight edge.
The board states: Select a remaining edge of G of minimum weight.
The second chosen edge is the edge joining y and x with weight 2, and it is added to the right-side tree.
It is the smallest remaining visible edge weight, and the speaker notes that a cycle cannot yet be formed with only two edges.
Apply step 3 by choosing a remaining minimum-weight edge that does not form a cycle with previously selected edges.
The board states: Select any remaining edge of G of minimum weight that does not form a cycle with the previously selected edges.
The third chosen edge is the edge joining w and v with weight 3, and it is added to the right-side tree.
The speaker explicitly says it does not create a cycle with the previous edges.
Compute how many total edges are required for the spanning tree.
The graph has vertices, and the algorithm stops after n-1 edges.
Check the remaining minimum-weight candidates for the fourth edge.
Step 3 must be repeated until four edges have been selected.
The edge joining u and w has weight 4 but is rejected.
The speaker says choosing it would create a cycle with the already selected edges.
The edge joining u and x has weight 4 and is selected as the fourth edge.
It is the only remaining minimum-weight edge that does not create a cycle.
For this example graph, the algorithm selects exactly four edges: uv, yx, wv, and ux, producing the spanning tree drawn on the right.
The narrator computes the weight verbally as 2 plus 4 plus 1 plus 3.
The screen shows beside the extracted tree.
The right-hand tree displays edge weights 2, 4, 1, and 3.
Add the weights of the four edges in the extracted tree.
By definition, the weight of a spanning tree is the sum of its edge weights.
The sum evaluates to 10.
Arithmetic evaluation of the displayed edge weights.
The first example's minimum spanning tree has total weight 10.
The narrator states, "The weight of mine is 21".
The screen writes .
The final tree on the right contains edges corresponding to weights 1, 2, 3, 4, and 11.
The intermediate addition is spoken as a final value rather than fully written out on screen.
Sum the weights of the five edges in the displayed spanning tree.
Use the definition of spanning-tree weight as the sum of edge weights.
The total is 21, matching the value written on screen and spoken by the narrator.
Arithmetic evaluation.
The second example's minimum spanning tree has total weight 21.
The narrator says, "To make this algorithm more concrete, let's try running it on this graph here."
A five-vertex weighted graph appears on the left, with isolated copies of the same five vertices on the right.
The algorithm steps remain pasted above the example for reference.
The clip ends before any edge is actually selected or rejected, so the worked solution is not completed within this segment.
Some edge weights are visually ambiguous in the sampled frames, but the clearly legible values include uv=1, vx=2, wy=3, uw=4, xy=5, yv=5, and xw=6; the remaining displayed weights are 4, 7, and 7 on edges ux, vw, and yx respectively.
Apply Kruskal's algorithm to the displayed five-vertex weighted graph with vertices u, v, w, x, y.
The graph has vertices u, v, w, x, y.
The visible edge weights are uv=1, vx=2, wy=3, uw=4, ux=4, xy=5, yv=5, xw=6, vw=7, yx=7.
The algorithm steps are pasted above the graph.
The right side shows the same five vertices isolated, ready to build the spanning tree.
Begin demonstrating how Kruskal's algorithm would select edges from this graph to form a minimum spanning tree.
The video replaces the pure text setup with a concrete graph example while keeping the algorithm steps visible above.
The narrator explicitly says the example is shown to make the algorithm more concrete.
The left graph is the source weighted graph; the right side displays the same vertices separately as the place where the spanning tree will be assembled.
This is directly visible in the diagram layout.
Before starting the selection process, the narrator reminds the viewer that a spanning tree must contain all vertices of the original graph.
This is stated in the audio at the end of the clip.
No final spanning tree is produced within this clip; the segment only sets up the example and restates the algorithm before execution begins.
The clip ends while the narrator is still introducing the example, so verification of the final MST is outside the provided interval.
A weighted graph with vertices u, v, w, x, y is shown on the left, and a duplicate vertex set on the right is used to build the spanning tree.
The speaker walks through the algorithm on this exact graph.
The visible edge weights include 1, 2, 3, 4, 5, 6, 7, and the stopping calculation is written.
Some edge labels are visually ambiguous in the drawing, but the spoken narration clearly identifies the chosen edges uv, yx, wv, and ux.
The full final tree is not verbally summarized before the clip ends, although the fourth edge is selected.
Run Kruskal's algorithm on the displayed weighted graph G with vertices u, v, w, x, y and construct the spanning tree on the duplicated vertex set at the right.
The graph G has 5 vertices: u, v, w, x, y.
Edge weights are written in green next to the edges.
The algorithm steps are written on the board.
The right side contains a duplicate copy of the vertices for recording selected edges.
Select edges in increasing weight order while avoiding cycles until n-1 edges have been chosen.
Start with step 1 and find the minimum-weight edge in the whole graph.
The board's first instruction is to select an edge of G of minimum weight.
Choose the edge between u and v and draw it on the right-side tree.
The speaker identifies this as the edge of minimum weight.
Move to step 2 and choose a remaining minimum-weight edge.
The board's second instruction is to select a remaining edge of G of minimum weight.
Choose the edge between y and x and add it to the right-side tree.
The speaker says this is the minimum-weight remaining edge and notes that two edges cannot yet form a cycle.
Move to step 3 and consider only remaining minimum-weight edges that do not create a cycle.
The board's third instruction adds the no-cycle condition.
Choose the edge between w and v and add it to the right-side tree.
The speaker explicitly checks that it does not create a cycle with the previous edges.
Compute the required number of edges for completion.
There are vertices, and the algorithm stops after n-1 edges.
Search the remaining edges of minimum weight for the fourth choice.
Step 3 must be repeated until four edges are selected.
Do not choose the edge between u and w.
The speaker says it would create a cycle with the already selected edges.
Choose the edge between u and x as the final edge needed in this clip.
It is the only remaining minimum-weight edge that does not create a cycle.
The spanning tree built in the clip consists of the edges uv, yx, wv, and ux.
The count matches the written stopping rule , and the right-side drawing shows exactly these four edges added in sequence.
A 5-vertex weighted graph with vertices u, v, w, x, y is shown on the left, and the extracted tree is shown on the right.
The screen writes and .
The narrator explains stopping after four edges and computing the tree weight as .
Apply Kruskal's algorithm to the displayed 5-vertex weighted graph and determine the weight of the resulting minimum spanning tree.
The graph has 5 vertices, so
The algorithm requires selected edges
The final tree shown has edge weights 2, 4, 1, and 3
Find the minimum spanning tree and compute .
Compute how many edges must be selected.
Kruskal's algorithm stops after n-1 edges have been chosen.
Add the weights of the edges in the selected tree.
The weight of a spanning tree is the sum of its edge weights.
The resulting minimum spanning tree has total weight 10.
Direct arithmetic from the displayed edge weights.
The minimum spanning tree has weight 10.
The narrator states that other spanning trees exist but none has weight less than 10.
A new 6-vertex weighted graph appears with vertices u, v, w, x, y, z and edge weights including 1, 2, 3, 4, 5, 6, 7, 8, 9, and 11.
The screen writes .
The narrator invites the viewer to run the algorithm and then says the weight is 21.
The exact sequence of edge selections is not fully narrated step-by-step in this clip; only the final tree and total weight are clearly presented.
Run Kruskal's algorithm on the second displayed weighted graph and find the weight of a minimum spanning tree.
The graph has 6 vertices
The final displayed tree has total weight 21
The narrator says this graph does not force an arbitrary tie choice
Determine the minimum spanning tree weight for the second graph.
Select minimum-weight edges while avoiding cycles until 5 edges are chosen.
This is the method stated on screen for Kruskal's algorithm.
The resulting tree weight is 21.
The narrator gives this value and the screen writes it explicitly.
The minimum spanning tree weight is 21.
The narrator says the viewer's tree should have the same weight because there is only one minimum weight for this graph.
The screen shows only typed and handwritten text on a black background, with a red pointer moving over words such as "minimum spanning tree", "connected weighted graph", "G", "n", and "T".
Visible text includes the title sentence and the setup "Let G be a connected weighted graph of order n. Kruskal's Algorithm finds a minimum spanning tree T in the following manner."
Title sentence about Kruskal's algorithm
Handwritten setup line defining G, n, and T
Red pointer dot
The red pointer moves across key terms in the title and setup sentence.
Around 30 seconds, the expression n-1 is written and boxed near the setup line.
The background remains black.
No graph drawing is present yet.
The mathematical content stays focused on definitions and notation.
This visual phase establishes the problem setting and notation before the algorithm steps are written out.
Four numbered handwritten steps appear beneath the setup text.
The steps read: 1. Select an edge of G of minimum weight; 2. Select a remaining edge of G of minimum weight; 3. Select any remaining edge of G of minimum weight that does not form a cycle with the previously selected edges; 4. Repeat 3. until n-1 edges have been selected.
The red pointer tracks along the lines as the narrator explains each step.
Numbered steps 1 through 4
Red pointer dot
Setup text above the steps
The full algorithm is revealed as four written steps.
The pointer emphasizes different phrases, especially the cycle condition in step 3 and the stopping condition in step 4.
The earlier setup text remains visible above the steps.
No example graph is shown during most of this interval.
The visual layout converts the verbal description into an explicit ordered procedure, highlighting the greedy minimum-weight rule and the acyclicity constraint.
A weighted graph with five yellow vertices labeled u, v, w, x, y appears on the left, and five isolated yellow vertices with the same labels appear on the right.
The algorithm steps are pasted above the example graph.
A blue circle briefly encloses the left graph around 95 seconds.
The clip ends before any edge is selected into the right-side tree.
The exact visual emphasis sequence after the blue circle is limited by the short remaining duration.
Left weighted graph on vertices u, v, w, x, y
Right isolated copy of the same five vertices
Pasted algorithm steps above
Blue circular highlight around the left graph
The screen changes from text-only explanation to a concrete graph example.
The left graph is temporarily circled in blue to draw attention to it.
The right-side isolated vertices are prepared as the destination for the spanning-tree construction.
The algorithm steps remain visible above the example.
The vertex labels on left and right match.
No edge has yet been transferred to the right side by the end of the clip.
This visual arrangement separates the source graph from the growing spanning tree, making the algorithm's edge-selection process easier to follow.
The screen is divided into a left weighted graph, a right duplicate vertex set, and algorithm text across the top.
left weighted graph G
right duplicated vertices u, v, w, x, y
top algorithm text
The left graph remains the source of candidate edges.
The right side remains the place where selected edges are recorded.
The algorithm text stays visible throughout.
The layout separates the input graph from the output spanning tree so each greedy choice can be tracked visually.
A red pointer moves to step 1, then to the bottom edge of the left graph, which is highlighted in purple.
A white edge is then drawn between u and v on the right.
step 1 text
edge uv on the left graph
right-side vertices u and v
The edge uv is highlighted on the left.
A corresponding edge is drawn on the right.
The other edges remain unselected at this moment.
This visual sequence implements the rule 'select an edge of G of minimum weight' by choosing uv with weight 1.
The pointer moves to step 2, then to the edge between y and x, which is highlighted in purple.
A white edge is drawn between y and x on the right.
step 2 text
edge yx on the left graph
right-side vertices y and x
The edge yx is highlighted on the left.
A corresponding edge is drawn on the right.
No cycle check is performed visually at this stage.
This shows the second greedy choice, with the speaker explaining that a cycle cannot yet occur with only two edges.
The pointer moves to step 3, then to the edge between w and v, which is highlighted in purple.
A white edge is drawn between w and v on the right.
step 3 text
edge wv on the left graph
right-side vertices w and v
The edge wv is highlighted on the left.
A corresponding edge is drawn on the right.
The previously selected edges uv and yx remain in the tree.
This visual step demonstrates the added restriction in step 3: choose a minimum-weight remaining edge only if it does not form a cycle.
Step 3 is boxed, then n-1 in step 4 is circled.
The expression is written beneath the algorithm text.
boxed step 3
circled n-1
written equation
The algorithm text is annotated to emphasize repetition and termination.
The numeric target 4 is written explicitly.
The graph still has five vertices.
The current tree still has three edges at the start of this annotation.
The annotations connect the general rule n-1 to the concrete example, showing that one more edge is needed.
The pointer indicates two remaining weight-4 edges, then the edge uw is marked as unusable, and finally the edge ux is highlighted and drawn on the right.
The exact visual marker used to reject uw is brief, but the spoken explanation clearly identifies it as the cycle-forming edge.
edge uw
edge ux
right-side tree
uw is considered and rejected.
ux is highlighted on the left and added on the right.
The earlier selected edges uv, yx, and wv remain unchanged.
This is the key cycle-avoidance demonstration: among equal minimum-weight candidates, the edge that would close a cycle is skipped and the other is chosen.
The left side shows the original 5-vertex graph with several edges highlighted in purple; the right side shows the extracted tree with four edges and weights 2, 4, 1, and 3.
A white outline is drawn around the right-hand tree, and red dots briefly mark selected edges during the explanation.
Original 5-vertex weighted graph
Extracted 4-edge tree
Algorithm text at top
Equation
Notation
The right-hand tree is isolated visually with an outline
Red markers briefly highlight edges being discussed
The weight notation is added beside the tree
The left graph remains the source graph
The right tree remains the selected spanning tree
The algorithm text stays visible above
The animation distinguishes the chosen minimum spanning tree from the full graph and visually supports the claim that the tree's total weight is 10.
The screen changes to a new 6-vertex weighted graph on the left and scattered labeled vertices on the right, then to a completed tree on the right.
Purple highlighting sweeps across parts of the left graph, and a white outline is drawn around the final tree on the right.
The precise order of edge additions is not fully legible from the sampled visuals alone.
Second 6-vertex weighted graph
Separated vertex labels on the right
Final spanning tree on the right
Equation
The first example is replaced by a new graph
The right side evolves from isolated vertices to a connected tree
The final tree is outlined and its weight is written as 21
The algorithm text remains on screen
The task is still to find a minimum spanning tree
The visual change marks a practice problem: apply the same algorithm to a larger graph and verify that the minimum total weight is 21.
The screen becomes a clean summary slide reading "Kruskal's Algorithm finds a minimum spanning tree in a connected weighted graph. Let G be a connected weighted graph of order n. Kruskal's Algorithm finds a minimum spanning tree T in the following manner. 1. Select an edge of G of minimum weight 2. Select a remaining edge of G of minimum weight 3. Select any remaining edge of G of minimum weight that does not form a cycle with the previously selected edges 4. Repeat 3. until n-1 edges have been selected".
Text-only summary of Kruskal's algorithm
Definitions of G, n, and T
Worked diagrams disappear
Only the formal algorithm statement remains
The algorithm steps are unchanged from earlier on-screen text
The clip closes by restating the method in compact formal form before mentioning future proof and related algorithms.
The narrator says that once two edges are selected, any additional edge could possibly create a cycle, and trees can't have cycles.
One might think any extra low-weight edge can be added freely while building a spanning tree.
The video explicitly rules this out: after the first two edges, each new edge must be checked so that it does not form a cycle, because a tree cannot have cycles.
The narrator reminds the viewer that a spanning tree by definition contains all the vertices of the original graph.
One might confuse a minimum-weight subgraph with a spanning tree and imagine that some vertices could be left out.
The video states that a spanning tree must contain all vertices of the original graph; Kruskal's algorithm only chooses edges to minimize total weight.
The speaker says that at this point we can select any edge of minimum weight because it's impossible that we'll create a cycle with just two edges.
One might assume every selected edge, including the second one, must be tested for cycle creation.
The video explicitly states that with only two edges selected, a cycle cannot yet be formed, so the second minimum-weight edge can be taken directly.
The speaker notes that the edges of minimum weight are these two that both have weight 4, but one cannot be picked because it would create a cycle.
When several remaining edges share the same minimum weight, one might think any of them may be chosen freely.
The example shows that even among equal-weight candidates, the no-cycle condition still decides: uw is rejected and ux is selected.
The narrator says, "there's only one minimum weight" and then clarifies, "this algorithm can produce different minimum spanning trees from the same graph since at times it is necessary to make an arbitrary choice among edges that are tied for the minimum weight."
Because the minimum spanning tree weight is unique, one might think the tree itself must always be unique.
The video distinguishes the two ideas: the minimum total weight is unique, but different minimum spanning trees can arise when tied minimum-weight edges force arbitrary choices.
The narrator says, "In a later video, we'll actually prove that the algorithm works".
One might assume the video has already established why Kruskal's algorithm always returns a minimum spanning tree.
The clip explicitly defers the correctness proof to a later video; here the algorithm is presented and illustrated by examples.
The narrator links the edge count n-1 to the stopping rule of the algorithm.
Step 4 uses n-1 as the termination condition.
The stopping rule in Kruskal's step 4 depends on the fact that a spanning tree on n vertices has exactly n-1 edges.
The narrator justifies step 3 by saying trees can't have cycles.
Step 3 is defined precisely to prevent the mistaken idea that extra edges may be added without regard to cycles.
The narrator says the example is introduced to make the algorithm more concrete.
The algorithm steps are pasted above the example graph.
The worked example is presented as a direct application of the previously stated Kruskal procedure.
The narrator states that a spanning tree contains all vertices of the original graph.
The right side shows all five vertices isolated before edge selection begins.
Understanding why all five vertices are copied to the right side depends on the definition that a spanning tree must include every vertex of the original graph.
Step 4 says repeat until n-1 edges have been selected.
The speaker links this count to completing the spanning tree.
The algorithm's stopping rule directly uses the fact that a spanning tree on n vertices contains n-1 edges.
Step 3 includes the phrase that does not form a cycle with the previously selected edges.
The later rejection of uw illustrates this condition in action.
The procedure contrasts the early stage, where a cycle check is unnecessary after only two edges, with the later stage, where cycle avoidance becomes essential.
The summary text states that Kruskal's Algorithm finds a minimum spanning tree T.
The narrator concludes, "So that's Kruskal's algorithm for finding a minimum spanning tree."
Kruskal's algorithm is presented as the method used to construct a minimum spanning tree.
The narrator defines as the sum of edge weights and then applies it in both examples.
The screen shows and later .
The definition of spanning-tree weight is used to compute the totals in the worked examples.
Step 4 of the algorithm states to repeat until n-1 edges have been selected.
The stopping rule is one component of the full description of Kruskal's algorithm.
The narrator mentions "my lesson on Prim's algorithm, which is a different, slightly more complicated algorithm for finding minimum spanning trees."
The video contrasts Kruskal's algorithm with Prim's algorithm as another method for finding minimum spanning trees.
The opening sentence names Kruskal's algorithm and minimum spanning tree.
The narrator repeats the same statement.
The narrator explains the n-1 edge count and the stopping condition.
The later written step 4 uses n-1 edges as the termination criterion.
The four handwritten algorithm steps are fully visible.
The narrator reads and explains each step in order.
The narrator says that after two edges, any additional edge could create a cycle.
Step 3 contains the no-cycle condition.
A five-vertex weighted graph is shown with vertices u, v, w, x, y.
The narrator introduces it as the graph on which to run the algorithm.
The worked solution is not completed in this clip.
The narrator says a spanning tree by definition contains all the vertices of the original graph.
Step 3 is written explicitly on the board.
The speaker explains that now we have to only consider edges that will not produce a cycle.
The board shows Repeat 3 until n-1 edges have been selected.
The speaker says one less edge than we have vertices because at that point we will have completed our spanning tree.
The speaker says we can't pick the edge joining u and w because that would create a cycle.
The edge uw is indicated and then the edge ux is chosen instead.
The speaker says it is impossible to create a cycle with just two edges.
The full algorithm text is displayed on screen.
The screen shows "Repeat 3. until n-1 edges have been selected" and the example writes .
Covered · Opening statement identifies Kruskal's algorithm as finding a minimum spanning tree in a connected weighted graph.
Covered · The setup introduces G, n, and T, and explains that a spanning tree on n vertices has n-1 edges, giving the stopping count.
Covered · Step 1 is written and explained: select an edge of minimum weight, with ties allowed.
Covered · Step 2 is written and explained: select another remaining edge of minimum weight.
Covered · Step 3 adds the no-cycle condition and the narrator explains why cycles must be avoided.
Covered · Step 4 says to repeat step 3 until n-1 edges have been selected, producing a minimum spanning tree.
Covered · A concrete five-vertex weighted example graph is introduced, with the algorithm pasted above and isolated vertices on the right; the clip ends before any edge selection is performed.
Covered · The board layout, weighted graph, duplicated vertices, and the four written algorithm steps are introduced.
Covered · Step 1 is applied and the edge uv of weight 1 is selected and drawn on the right.
Covered · Step 2 is applied; the edge yx of weight 2 is selected, with the explanation that two edges cannot yet form a cycle.
Covered · Step 3 is introduced and applied to select wv of weight 3 after checking that it does not create a cycle.
Covered · The stopping condition n-1 is emphasized and specialized to for this graph.
Covered · Among the remaining weight-4 edges, uw is rejected for creating a cycle and ux is selected as the fourth edge.
Covered · Opening states the n-1 stopping condition and identifies the first example's output as a minimum spanning tree.
Covered · Defines and computes the first example's tree weight as 10.
Covered · States that no other spanning tree of the first graph has smaller weight.
Covered · Introduces a second graph and invites the viewer to apply the same algorithm.
Covered · Gives the second example's minimum spanning tree weight as 21.
Covered · Explains that tied minimum-weight choices can yield different trees, but not for this example graph.
Covered · Restates the algorithm formally and says the correctness proof is deferred to a later video.
Covered · Mentions Prim's algorithm as a different method for minimum spanning trees.
Covered · Outro music and end-card visuals with no additional mathematical content.
Reviewed English material v1: knowledge_item "Scope of Kruskal's algorithm" at 0:00 — The video defines the setting for Kruskal's algorithm as a connected weighted graph, and states that the algorithm's output is a minimum spanning tree for that graph.
Bilibili7:44.113999999999976Another application of Graphs.
Graphs
YouTube4:02Another application of Graphs.
GraphsYouTube4:02Next in Graph Theory: Graphs → Vertex degrees.
Vertex degrees · View learning sequenceBilibili7:44.113999999999976Lecture for Graphs, compared with the current whiteboard.
GraphsYouTube4:02Lecture for Graphs, compared with the current whiteboard.
Graphs
YouTube15:26Explanation of Graphs, complementing the current application.
Graphs