Connectedness and Strongly Connected Graphs

1. Caption evidence
   Observation

   The phrase 'N vertices' appears in the exam point description.

N

the number of vertices in the graph

positive integer

1. Caption evidence
   Observation

   The phrase 'e edges' appears in the exam point description.

e

the number of edges in the graph

nonnegative integer

1. Diagram
   Observation

   Vertices in the graph are labeled with letters A, B, C, D, E

A, B, C, D, E

vertex labels in the example graph

discrete set

1. Formula
   Observation

   The board notes include phrases such as 'for an undirected graph G with N vertices', 'has at least n minus 1 edges', and 'has at most n times (n minus 1) divided by 2'.

1. The video uses both uppercase N and lowercase n to denote the number of vertices, without clarifying whether they are strictly synonymous.

n

the number of vertices in the graph

a positive integer

1. Formula
   Observation

   The board writes: 'If G is a connected graph' and 'If G is a strongly connected graph'.

G

the graph under discussion

an undirected or directed graph

1. Diagram
   Observation

   In the top example diagram and in Diagram 1 and Diagram 2 below, all vertices are labeled A, B, C, D, and E.

2. Audio
   Observation

   The instructor repeatedly says 'A can go to B and then to C', 'B can reach A', and so on.

A, B, C, D, E

the vertex labels in the example diagram

elements of the vertex set

1. Caption evidence
   Observation

   Expressions such as 'N vertices', '$n-1$ edges', '$n\cdot (n-1)/2$', '($n-1$)·($n-2$)/2', and '$n\cdot (n-1)$' appear in the exam point description.

2. Audio
   Observation

   During the explanation, the number of vertices from a concrete example is substituted as $n = 5$, illustrating: 'Here, n equals 5—that is, five vertices.'

n

The number of vertices in the graph

A positive integer; in the concrete example of this segment, $n = 5$

1. Caption evidence
   Observation

   The exam point description states: 'For an undirected graph G with N vertices' and 'In a directed graph G with N vertices.'

G

The graph under discussion; in this segment, it refers to both undirected and directed graphs, and its type must be inferred from context

1. Caption evidence
   Observation

   If G is a connected graph, then it has at least $n-1$ edges.

2. Audio
   Observation

   The instructor draws 5 vertices and connects them with 4 edges, saying: 'Five vertices use four edges.'

n-1

The minimum number of edges in an undirected connected graph with n vertices

1. Caption evidence
   Observation

   The maximum is $n\cdot (n-1)/2$.

2. Formula
   Observation

   The board displays $4+3+2+1 = (5\cdot 4)/2$, and the instructor verbally links it to the complete graph.

$\frac{n(n-1)}{2}$

The number of edges in an undirected complete graph with n vertices, which is also the maximum number of edges in an undirected simple graph

1. Caption evidence
   Observation

   If it is a disconnected graph, then z can have at most ($n-1$)×($n-2$)/2 edges.

2. Audio
   Observation

   The instructor constructs an example: let 5 vertices form a complete graph, and let the other vertex be disconnected from all of the first 5 vertices.

1. The subtitle reads 'z can have at most', but z is not defined elsewhere in this segment; this appears to be a typesetting placeholder or a typo.

$\frac{(n-1)(n-2)}{2}$

Maximum number of edges possible in an undirected disconnected graph with n vertices

1. Caption evidence
   Observation

   In a directed graph G with N vertices, if G is strongly connected, then it has at least n edges (a cycle).

2. Diagram
   Observation

   The example of a 'strongly connected graph' on the right is a directed cycle on 5 vertices.

n

Minimum number of edges in a strongly connected directed graph with n vertices; stated in the segment as a 'cycle'.

1. Audio
   Observation

   Okay, let us now look at the definition of a connected graph. If every pair of vertices in the graph is connected, then the graph is called connected; otherwise, it is disconnected.

2. Caption evidence
   Observation

   If every pair of vertices in the graph is connected, then the graph is called connected; otherwise, it is disconnected.

In an undirected graph, if there exists a path between every pair of vertices, the graph is called connected; otherwise, it is disconnected.

1. Applies to undirected graphs

1. Audio
   Observation

   In a strongly connected graph, every pair of vertices is mutually reachable; such a graph is called strongly connected.

2. Caption evidence
   Observation

   If every pair of vertices in a graph is mutually reachable, the graph is called strongly connected.

In a directed graph, if there exists a bidirectional path between every pair of vertices (i.e., a path from u to v and a path from v to u), the graph is called strongly connected.

1. Applies to directed graphs

1. Caption evidence
   Observation

   If G is connected, it has at least n minus 1 edges and at most n times (n minus 1) divided by 2 edges.

For an undirected graph G with N vertices, if G is connected, it has at least N minus 1 edges and at most N times (N minus 1) divided by 2 edges.

1. G is an undirected connected graph

1. definition of a connected graph

1. Caption evidence
   Observation

   If G is disconnected, the number of edges e can be at most (n minus 1) times (n minus 2) divided by 2.

For an undirected graph G with N vertices, if G is disconnected, then the number of edges e can be at most (N-1)*(N-2)/2.

1. G is an undirected disconnected graph

1. definition of a connected graph

1. Caption evidence
   Observation

   In a directed graph G with N vertices, if G is strongly connected, then it has at least N edges (forming a cycle) and at most $N*(N-1)$.

For a directed graph G with N vertices, if G is strongly connected, then it has at least N edges (forming a cycle) and at most $N*(N-1)$ edges.

1. G is a directed strongly connected graph

1. Definition of a strongly connected graph

1. Formula
   Observation

   The left side of the board states: 'If every pair of vertices in the graph is connected, then the graph is called connected; otherwise, it is disconnected.'

2. Diagram
   Observation

   The left example is an undirected graph, with vertices A, B, C, D, and E connected by undirected edges.

The video defines a connected graph as an undirected graph in which there exists a path between every pair of vertices; if even one pair of vertices is not connected, the graph is called disconnected.

1. Applies to undirected graphs

2. Requires that every pair of vertices be connected

1. Formula
   Observation

   The right board states: "If every pair of vertices in the graph is strongly connected, then the graph is called a strongly connected graph."

2. Diagram
   Observation

   The right example is a directed graph, with vertices A, B, C, D, and E connected by directed arrows.

3. Audio
   Observation

   The instructor says, "A can go to B, then to C… C can go to D, then to A… A and C are also strongly connected," and concludes, "Every pair of vertices is strongly connected, so this graph is a strongly connected graph."

The video defines a strongly connected graph as a directed graph in which every pair of vertices can reach each other via directed paths. The method of verification is to check, for each pair, whether bidirectional reachability exists.

1. Applies to directed graphs

2. Requires that every pair of vertices be strongly connected

1. Connected graph

1. Formula
   Observation

   Board writing key point: 'For an undirected graph G with N vertices, if G is connected, then the minimum number of edges is n minus 1, and the maximum is n times (n minus 1) divided by 2; if G is disconnected, then the maximum possible number of edges is (n minus 1) times (n minus 2) divided by 2.'

2. Audio
   Observation

   The instructor reads: 'In an undirected graph, if G is connected, then it has at least n minus one edge,' and asks, 'When does this minimum occur? It occurs when the graph resembles a tree.'

1. The video only verbally explains that the minimum number of edges corresponds to a structure resembling a tree, without providing a formal proof.

The video gives the extremal numbers of edges for an undirected graph with n vertices under two cases: when connected — minimum n minus 1 edges, maximum equal to the number of edges in a complete graph, n times (n minus 1) divided by 2; when disconnected — maximum (n minus 1) times (n minus 2) divided by 2 edges.

1. G is an undirected graph with n vertices

2. Separately considering the two cases: G connected and G disconnected

1. Connected graph

1. Formula
   Observation

   The last line written on the board: 'In a directed graph G with N vertices, if G is strongly connected, then the minimum number of edges is n (forming a cycle), and the maximum is n times (n minus 1).'

1. Within this segment, the video does not fully prove why the minimum number of edges is n (with the parenthetical note 'cycle'); it only gives an intuitive illustration using a three-vertex cycle earlier.

The video gives the extremal numbers of edges for a directed graph with n vertices when strongly connected: minimum n edges, with the parenthetical hint 'cycle' indicating the minimal structure; maximum n times (n minus 1) edges — meaning that for any two distinct vertices, both directions of the directed edge may exist.

1. G is a directed graph with n vertices

2. G is a strongly connected graph.

1. Strongly connected graph

1. Caption evidence
   Observation

   If any two vertices in a graph are connected, the graph is called connected; otherwise, it is disconnected.

2. Diagram
   Observation

   The left-side title reads 'Connected Graph', accompanied by an example of an undirected graph with 5 vertices.

The segment defines an undirected graph: if there exists a path between any two vertices in the graph, it is called a connected graph; if there exist two vertices that are not connected, it is called a disconnected graph. The left-side example visually illustrates this concept using a green undirected graph.

1. The object is an undirected graph

2. The criterion for judgment is whether 'any two vertices' are connected

1. Caption evidence
   Observation

   If any pair of vertices in a graph is strongly connected, the graph is called strongly connected.

2. Diagram
   Observation

   The right-side title reads 'Strongly Connected Graph', accompanied by an example of a directed cycle with 5 vertices.

The segment defines a directed graph as strongly connected if every pair of vertices is mutually reachable. The right-hand example uses an orange directed cycle to show that each vertex can reach every other vertex along directed edges.

1. The object is a directed graph

2. It requires mutual reachability between every pair of vertices

1. Caption evidence
   Observation

   If G is a connected graph, then it has at least n minus 1 edges.

2. Audio
   Observation

   The instructor draws 5 points and connects them with 4 edges, saying, "Five vertices use four edges."

3. Diagram
   Observation

   With a red pen, the instructor draws five points labeled A, B, C, D, and E on blank space, and draws 4 edges emanating from point C.

For an undirected graph G with n vertices, if G is connected, then its number of edges is at least n minus 1. The segment illustrates this using the example n equals 5: 5 vertices require at least 4 edges to remain connected.

1. G is an undirected graph

2. G has n vertices

3. G is connected

1. Connected graphs and disconnected graphs

1. Audio
   Observation

   The instructor says: "Clearly, Graph One is not, because A can reach D, but D cannot reach A in return; therefore, it is not a strongly connected graph."

2. Diagram
   Observation

   In Graph 1, there is a directed edge from A to D, and no directed path from D back to A.

Graph 1 is not strongly connected, because there exist vertices A and D such that A can reach D but D cannot reach A.

1. Graph 1 is a directed graph.

2. There exists a directed edge from A to D in the graph.

3. There is no directed path from D back to A.

There exists a pair of vertices (A, D) that are not mutually reachable.

1. Audio
   Observation

   The instructor says: "Graph Two is certainly not either... B can reach A, but how can A reach B? It cannot; therefore, Graph Two is also not a strongly connected graph."

2. Diagram
   Observation

   In Graph 2, the edges $B\to A$, $B\to C$, and $C\to A$ are all directed edges, and there is no directed path from A back to B.

Graph 2 is not strongly connected because there exist vertices A and B such that B can reach A but A cannot reach B.

1. Graph 2 is a directed graph.

2. There exists a directed path from B to A.

3. There does not exist a directed path from A to B.

There exists a pair of vertices (A, B) that are not mutually reachable.

1. Audio
   Observation

   The instructor says: "Unless he changes this arrow... so that it forms a cycle, then it becomes a strongly connected graph, and in this case its number of edges is minimal."

2. Diagram
   Observation

   The instructor adds a reverse arrow to graph 2 so that A, B, and C form a directed cycle.

1. The video does not provide a general proof, only an intuitive example using a three-vertex cycle.

After adjusting the edge directions in graph 2 to form a directed cycle, the graph becomes strongly connected; in this example, such a structure has the minimal number of edges.

1. In the modified graph, A, B, and C form a directed cycle.

2. On the cycle, every vertex can reach all other vertices by following the direction.

Specific modifications to this example diagram

1. Caption evidence
   Observation

   If G is a connected graph, then it has at least $n-1$ edges.

2. Audio
   Observation

   The instructor supports this conclusion using an example with 5 vertices and 4 edges.

If G is an undirected connected graph with n vertices, then |$E(G)$| ≥ $n-1$.

1. G is an undirected graph

2. G has n vertices

3. G is connected

holds for all undirected connected graphs G satisfying the premise

1. Caption evidence
   Observation

   at most $n*(n-1)/2$.

2. Audio
   Observation

   The instructor interprets this as the number of edges in a complete graph.

If G is an undirected simple graph with n vertices, then |$E(G)$| ≤ $n(n-1)/2$.

1. G is an undirected simple graph

2. G has n vertices

holds for all undirected simple graphs with n vertices

1. Caption evidence
   Observation

   If it is a disconnected graph, then it can have at most (n-1)*(n-2)/2 edges.

2. Audio
   Observation

   The instructor demonstrates that this upper bound is attainable by constructing a graph where 5 vertices form a complete graph and the 6th vertex is isolated.

1. The letter z in the subtitle is undefined and appears to be a typo.

If G is an undirected disconnected simple graph with n vertices, then |$E(G)$| ≤ ($n-1$)($n-2$)/2.

1. G is an undirected simple graph

2. G has n vertices

3. G is disconnected

Holds for all undirected disconnected graphs satisfying the premise

1. Caption evidence
   Observation

   In a directed graph G with N vertices, if G is strongly connected, then G has at least n edges (a cycle).

2. Diagram
   Observation

   The directed cycle on the right shows strong connectivity achieved with n edges on n vertices.

If G is a directed strongly connected graph with n vertices, then |$E(G)$| ≥ n.

1. G is a directed graph

2. G has n vertices

3. G is strongly connected

holds for all directed strongly connected graphs satisfying the premise

1. Caption evidence
   Observation

   at most n times (n minus 1).

1. The segment does not provide a proof, only the concluding statement.

If G is a directed strongly connected simple graph with n vertices, then |$E(G)$| ≤ n(n minus 1).

1. G is a directed simple graph

2. G has n vertices

3. G is strongly connected

holds for all directed strongly connected graphs satisfying the premise

1. Formula
   Observation

   The slide text explicitly states this conclusion.

For an undirected graph G with n vertices, if G is connected, then it has at least n minus1 edges and at most n times n minus1 over2 edges.

1. G is an undirected graph

2. G has n vertices

3. G is connected

Holds for all n and G satisfying the premises

1. Formula
   Observation

   The slide text explicitly states this conclusion.

For an undirected graph G with n vertices, if G is disconnected, then it can have at most the quantity n minus 1 times the quantity n minus 2, all divided by 2 edges.

1. G is an undirected graph.

2. G has n vertices.

3. G is disconnected.

Holds for all n and G satisfying the premises.

1. Formula
   Observation

   The slide text explicitly states this conclusion.

In a directed graph G with n vertices, if G is strongly connected, then it has at least n edges and at most $n(n-1)$ edges.

1. G is a directed graph.

2. G has n vertices.

3. G is strongly connected.

Holds for all n and G satisfying the premises.

1. Audio
   Observation

   For example, consider vertices A and D: one can go from A to C, then from C to D; thus, A and D are considered connected. Also, there exist paths between A and B, C, E, and so on. Therefore, this graph is a connected graph.

2. Animation
   Observation

   The instructor traces the path A-C-D in red on the undirected graph on the left

1. Expression

   $$A \to C \to D$$
   Explanation

   finding a path between vertices A and D

   Justification

   connectivity means existence of a path; direct adjacency is not required

   Shown in the video
2. Expression

   $$\forall u, v \in V, \exists P(u, v)$$
   Explanation

   There exists a path between any two vertices in the graph.

   Justification

   It satisfies the definition of a connected graph.

   Derived from the video

This undirected graph is a connected graph.

1. Audio
   Observation

   The presenter checks each pair in the directed graph above: 'A can go to B and then to C... C can go to D and then to A... Similarly, A and E are strongly connected, A and D are strongly connected, and also B and C, B and E, B and D, C and E, C and D, E and D are all strongly connected.'

2. Diagram
   Observation

   In the directed graph on the upper right, there exists a path following arrow directions between every pair of vertices.

1. Expression

   $$A \to B \to C$$
   Explanation

   First, explain that A can reach C via a directed path.

   Justification

   Based on the arrow directions in the diagram and the presenter's verbal path description.

   Shown in the video
2. Expression

   $$C \to D \to A$$
   Explanation

   Then, explain that C can return to A via a directed path, so A and C are mutually reachable.

   Justification

   Based on the arrow directions in the diagram and the presenter's verbal path description.

   Shown in the video
3. Expression

   $$\forall u,v \in V,\ u \leftrightarrow v$$
   Explanation

   Next, the presenter continues listing vertex pairs—A and E, A and D, B and C, B and E, B and D, C and E, C and D, E and D—and explains that each pair is strongly connected.

   Justification

   According to the definition of a strongly connected graph: every pair of vertices is strongly connected.

   Shown in the video
4. Expression

   $$\text{this directed graph is strongly connected}$$
   Explanation

   Since all vertex pairs are mutually reachable, conclude accordingly.

   Justification

   Apply the definition of a strongly connected graph directly.

   Shown in the video

The directed graph in the upper right satisfies strong connectivity for any pair of vertices, so it is a strongly connected graph.

1. Audio
   Observation

   The instructor points out, "A can reach D, but D cannot go back to A."

2. Diagram
   Observation

   In graph 1, D is a sink vertex with only incoming edges and no arrows leaving D.

1. Expression

   $$A \to D$$
   Explanation

   There exists a directed path from A to D in the graph.

   Justification

   Read directly from the graph.

   Shown in the video
2. Expression

   $$D \not\to A$$
   Explanation

   However, there is no directed path from D back to A in the graph.

   Justification

   Read directly from the graph: D has no outgoing edges.

   Shown in the video
3. Expression

   $$\neg(A \leftrightarrow D)$$
   Explanation

   Therefore, A and D are not a strongly connected pair of vertices.

   Justification

   Strong connectivity requires mutual reachability.

   Shown in the video
4. Expression

   $$\text{graph one is not strongly connected}$$
   Explanation

   If even one pair of vertices fails mutual reachability, the entire directed graph is not strongly connected.

   Justification

   Negation of the definition of a strongly connected graph.

   Shown in the video

Graph 1 is not strongly connected.

1. Audio
   Observation

   The instructor says, "B can reach A, but how can A reach B? That's impossible."

2. Diagram
   Observation

   In graph 2, there are directed edges $B\to A$, $B\to C$, and $C\to A$; vertex A has no outgoing edges to other vertices.

1. Expression

   $$B \to A$$
   Explanation

   There exists a directed path from B to A in the graph.

   Justification

   Read the graph directly.

   Shown in the video
2. Expression

   $$A \not\to B$$
   Explanation

   But A has no outgoing edges, so it cannot return to B along the arrows.

   Justification

   Read the graph directly.

   Shown in the video
3. Expression

   $$\neg(B \leftrightarrow A)$$
   Explanation

   Therefore, B and A do not satisfy strong connectivity.

   Justification

   Strong connectivity requires mutual reachability.

   Shown in the video
4. Expression

   $$\text{graph two is not strongly connected}$$
   Explanation

   Since there exists a pair of vertices that cannot reach each other, the entire graph is not strongly connected.

   Justification

   Negation of the definition of a strongly connected graph.

   Shown in the video

Figure 2 is not strongly connected.

1. Audio
   Observation

   The instructor says, "Let’s reverse this arrow… B can reach C, C can reach A, and A can reach B, forming a cycle; then it becomes a strongly connected graph."

2. Diagram
   Observation

   The instructor adds reverse-directed arrows to Figure 2, forming a directed cycle among A, B, and C.

1. Expression

   $$B \to C \to A \to B$$
   Explanation

   After modification, the three vertices form a closed directed cycle in the same direction.

   Justification

   Based on the figure after the instructor added the arrows.

   Shown in the video
2. Expression

   $$\forall u,v \in \{A,B,C\},\ u \leftrightarrow v$$
   Explanation

   In a directed cycle, any two vertices can reach each other following the cycle’s direction.

   Justification

   An intuitive illustration of reachability in a cycle.

   Derived from the video
3. Expression

   $$\text{the modified graph is strongly connected}$$
   Explanation

   Since all three pairs of vertices are mutually reachable, the definition of a strongly connected graph is satisfied.

   Justification

   Applying the definition of a strongly connected graph.

   Shown in the video

After converting Figure 2 into a directed cycle, it becomes a strongly connected graph; the video further states that this structure has the minimum number of edges.

1. Audio
   Observation

   The instructor says, in sequence: "A connects to the other four vertices, using four edges," "then B connects to the other three vertices, using three edges," "four plus three plus two plus one."

2. Formula
   Observation

   The blackboard writes 4 plus 3 plus 2 plus 1 equals (5 times 4) divided by 2.

3. Diagram
   Observation

   The green complete graph on the left is circled in red to assist counting.

1. Expression

   $$4+3+2+1$$
   Explanation

   For a complete graph with 5 vertices, 4 edges can be drawn from the first vertex; after removing already-counted edges, the second vertex contributes 3 new edges, the third contributes 2 new edges, and the fourth contributes 1 new edges.

   Justification

   Counting layer by layer according to vertex order avoids double-counting any undirected edge.

   Shown in the video
2. Expression

   $$\frac{5\cdot 4}{2}$$
   Explanation

   Viewing $4+3+2+1$ as an arithmetic sequence with first term 4, last term 1, and 4 terms, it can also be written as ($5\cdot 4$)/2.

   Justification

   The instructor verbally uses the 'first term plus last term' approach for summing arithmetic sequences and writes this result on the board.

   Shown in the video
3. Expression

   $$\frac{n(n-1)}{2}$$
   Explanation

   Replacing the specific 5 in the example with the general number of vertices n yields the edge-count formula for a complete graph with n vertices.

   Justification

   Generalizing from a specific case to a general formula; the text of this segment directly gives the closed-form expression.

   Shown in the video

An undirected complete graph with n vertices has $n(n-1)/2$ edges, so this is also the maximum number of edges in an undirected simple graph.

1. Audio
   Observation

   The instructor says, 'We want this graph to be disconnected yet have the maximum possible number of edges, so let these five vertices—A, B, C, D, and E—form a complete graph, and … let F be disconnected from A, B, C, D, and E.'

2. Diagram
   Observation

   In red ink, vertices A, B, C, D, and E are circled together, while F stands alone outside the circle.

1. This segment only explains the construction idea and does not proceed to the final numerical calculation.

1. Expression

   $$K_{n-1}$$
   Explanation

   To maximize the number of edges while keeping the graph disconnected, first connect all pairs among $n-1$ vertices to form a complete subgraph.

   Justification

   Among all graphs with a given number of vertices, a complete graph has the maximum number of edges.

   Shown in the video
2. Expression

   $$\frac{(n-1)(n-2)}{2}$$
   Explanation

   The number of edges inside these $n-1$ vertices is ($n-1$)($n-2$)/2.

   Justification

   Apply the formula for the number of edges in a complete graph derived earlier.

   Derived from the video
3. Expression

   $$v \text{ isolated}$$
   Explanation

   The remaining nth vertex is isolated—unconnected to any other vertex—so the entire graph remains disconnected.

   Justification

   An isolated vertex ensures no path exists between components.

   Shown in the video

Thus, a disconnected undirected graph with n vertices can have at most ($n-1$)($n-2$)/2 edges.

1. Audio
   Observation

   The instructor says, 'Because the total number of vertices is six,' 'The final answer is five halves times four,' 'That is, n minus one over two, multiplied by n minus two,' 'Because it is based on a complete graph with n minus one vertices,' 'Originally there are n vertices; we remove one vertex, leaving n minus one vertices,' 'The number of edges in a complete graph on n minus one vertices is n times n minus one over two,' 'If this single isolated vertex has an edge to or from any of the other five vertices, then the graph cannot be disconnected.'

2. Animation
   Observation

   The instructor circles 6 in blank space and writes hints such as n, $n-1$, $n-2$, while giving a verbal explanation.

1. The instructor's spoken transition from 'n over two times n minus one' to the final formula 'n minus one over two times n minus two' is somewhat quick, but overall points to the remaining $n-1$ vertices forming a complete graph.

1. Expression

   $$$$
   Explanation

   First treat one vertex as an isolated vertex to keep the graph disconnected.

   Justification

   The instructor says 'originally there were n vertices, minus this one position', meaning selecting one vertex separately from the n vertices.

   Shown in the video
2. Expression

   $$$$
   Explanation

   The number of remaining vertices is $n-1$.

   Justification

   The instructor explicitly states 'the number of remaining vertices is n minus one vertex'.

   Shown in the video
3. Expression

   $$\frac{(n-1)(n-2)}{2}$$
   Explanation

   To maximize the total number of edges, connect every pair among these $n-1$ remaining vertices, forming a complete graph.

   Justification

   The instructor says 'the number of edges in the complete graph corresponding to n minus one vertex is just...', then gives the answer as 'n minus one over two times n minus two'.

   Shown in the video
4. Expression

   $$$$
   Explanation

   If this isolated vertex is connected to any other vertex, the graph is no longer disconnected.

   Justification

   The instructor says 'if this single vertex is connected to any one of these five vertices below, then it cannot be a disconnected graph'.

   Shown in the video

Therefore, a disconnected undirected graph with n vertices has at most $\frac{(n−1)(n−2)}{2}$ edges.

1. Audio
   Observation

   The instructor says, 'Make it a cycle,' 'A, B, C, D,' 'A points to C, C points to D, D points to B, B points to A,' 'In this case, the number of edges is minimized,' 'n vertices correspond to n edges—for example, four vertices correspond to four edges.'

2. Animation
   Observation

   The instructor draws four vertices A, B, C, D and directed arrows on blank space, forming a cyclic structure.

1. The spoken phrase 'A points to C, C points to D, D points to B, B points to A' does not exactly match the cyclic order drawn in the figure, but both convey the core idea of 'forming a cycle.'

1. Expression

   $$$$
   Explanation

   Take n vertices and connect them sequentially in a directed cycle.

   Justification

   The instructor says, 'Make it a cycle.'

   Shown in the video
2. Expression

   $$$$
   Explanation

   Each vertex on the cycle has exactly one outgoing edge and one incoming edge; the entire graph has n edges.

   Justification

   The instructor concludes, 'n vertices correspond to n edges.'

   Shown in the video
3. Expression

   $$$$
   Explanation

   In this directed cycle, any two vertices can reach each other along the cycle, so the graph is strongly connected.

   Justification

   This is the direct meaning of using the 'cyclic' construction to illustrate the minimum number of edges for strong connectivity.

   Derived from the video

Therefore, a strongly connected directed graph with n vertices requires at least n edges.

1. Audio
   Observation

   The instructor says, 'The maximum is n times (n minus one),' 'This maximum case matches the property we discussed earlier: the maximum is one-half times n times (n minus one),' 'Because in a directed graph there are two edges— one pointing forward and one pointing backward—so we multiply by two on top of that.'

1. Expression

   $$\frac{n(n-1)}{2}$$
   Explanation

   First, recall the number of edges in a complete undirected graph with n vertices.

   Justification

   The instructor explicitly cites "at most n times n minus one, all over two".

   Shown in the video
2. Expression

   $$2 \times \frac{n(n-1)}{2}=n(n-1)$$
   Explanation

   In a directed graph, there can be two edges between each pair of vertices, pointing in opposite directions.

   Justification

   The instructor says "one points forward and one points backward, so we multiply the previous result by two".

   Shown in the video

Therefore, the maximum number of edges in a directed graph with n vertices is n times n minus 1.

1. Diagram
   Observation

   The left side shows an undirected graph with five vertices: A, B, C, D, and E.

2. Audio
   Observation

   The instructor uses A and D as an example, explaining that although there is no direct edge between them, there exists a path A-C-D, so they are connected.

Determine whether a given undirected graph is a connected graph.

1. The undirected graph contains vertices A, B, C, D, and E.

2. The edges include (A,B), (A,C), (B,C), (C,D), (C,E), (D,E), and others.

Verify whether a path exists between any two vertices.

1. Expression

   $$A \to C \to D$$
   Explanation

   Verify whether a path exists between A and D.

   Justification

   A path can be found via the intermediate vertex C.

   Shown in the video
2. Expression

   $$\text{The same reasoning applies to other pairs of points}$$
   Explanation

   Verify whether a path exists between any other pair of vertices

   Justification

   Observing the graph, we see that all vertices belong to the same connected component

   Shown in the video

This graph is a connected graph

A path can be found between any pair of vertices

1. Diagram
   Observation

   The directed graph in the upper right, with vertices A, B, C, D, and E.

2. Audio
   Observation

   The instructor verifies strong connectivity for every pair of vertices one by one.

Determine whether the directed graph on the upper right is strongly connected.

1. The graph is a directed graph.

2. The vertices are A, B, C, D, and E.

3. The graph contains several directed edges, which can be traversed following the arrow directions.

Verify whether every pair of vertices is strongly connected.

1. Expression

   $$A \to B \to C,\ C \to D \to A$$
   Explanation

   First verify mutual reachability between A and C.

   Justification

   Read the graph and follow the instructor's verbal description of paths.

   Shown in the video
2. Expression

   $$A \leftrightarrow E,\ A \leftrightarrow D,\ B \leftrightarrow C,\ B \leftrightarrow E,\ B \leftrightarrow D,\ C \leftrightarrow E,\ C \leftrightarrow D,\ E \leftrightarrow D$$
   Explanation

   Continue checking whether all remaining vertex pairs are also mutually reachable.

   Justification

   The instructor lists each of these vertex pairs as strongly connected, one by one.

   Shown in the video
3. Expression

   $$\text{every pair of vertices is strongly connected}$$
   Explanation

   All vertex pairs satisfy mutual reachability.

   Justification

   Definition of a strongly connected graph.

   Shown in the video

This graph is strongly connected.

Verification is completed by checking directed paths between every pair of vertices.

1. Diagram
   Observation

   The directed graph below, labeled "Graph 1", has vertices A, B, C, and D, where $A\to D$ is a unidirectional edge.

2. Audio
   Observation

   The instructor says, "A can reach D, but D cannot go back to A."

Determine whether Graph 1 is strongly connected.

1. Graph 1 is a directed graph.

2. There exists a directed path from A to D.

3. There is no directed path from D back to A.

Determine whether Graph 1 satisfies strong connectivity for every pair of vertices.

1. Expression

   $$A \to D$$
   Explanation

   A can reach D.

   Justification

   Read the graph directly.

   Shown in the video
2. Expression

   $$D \not\to A$$
   Explanation

   D cannot return to A.

   Justification

   Read the graph directly.

   Shown in the video
3. Expression

   $$\neg(A \leftrightarrow D)$$
   Explanation

   Therefore, A and D do not satisfy strong connectivity.

   Justification

   Strong connectivity requires mutual reachability.

   Shown in the video

Graph 1 is not a strongly connected graph.

To disprove overall strong connectivity, it suffices to find one pair of vertices that cannot reach each other.

1. Diagram
   Observation

   The "Graph 2" below is a directed graph with vertices A, B, and C, and edge directions $B\to A$, $B\to C$, and $C\to A$.

2. Audio
   Observation

   The instructor says, "B can reach A, but how can A reach B? It cannot."

Determine whether Graph 2 is a strongly connected graph.

1. Graph 2 is a directed graph.

2. There exists a directed path from B to A.

3. A has no outgoing path back to B.

Determine whether graph 2 satisfies strong connectivity for every pair of vertices.

1. Expression

   $$B \to A$$
   Explanation

   B can reach A.

   Justification

   Read the graph directly.

   Shown in the video
2. Expression

   $$A \not\to B$$
   Explanation

   A cannot reach B.

   Justification

   Read the graph directly.

   Shown in the video
3. Expression

   $$\neg(B \leftrightarrow A)$$
   Explanation

   Therefore, B and A do not satisfy strong connectivity.

   Justification

   Strong connectivity requires mutual reachability.

   Shown in the video

Graph 2 is not strongly connected.

Negate it by identifying a pair of vertices that cannot reach each other.

1. Diagram
   Observation

   The instructor adds reverse arrows to graph 2, forming a directed cycle among A, B, and C.

2. Audio
   Observation

   The presenter says, 'B can reach C, C can reach A, and A can reach B; this forms a cycle, making it a strongly connected graph, and in this case, its number of edges is minimal.'

How to change the direction of edges in graph 2 to make it strongly connected, and observe the property of its number of edges.

1. Original graph 2 is a directed graph

2. Vertices are A, B, and C

3. The presenter may manually add arrows

Construct a strongly connected version and explain that its number of edges is minimal.

1. Expression

   $$B \to C \to A \to B$$
   Explanation

   Change the edges to form a directed cycle with all edges oriented in the same direction.

   Justification

   Based on the diagram after the presenter's manual additions.

   Shown in the video
2. Expression

   $$\forall u,v \in \{A,B,C\},\ u \leftrightarrow v$$
   Explanation

   Any two vertices on the cycle can reach each other along the cycle.

   Justification

   Reachability in a directed cycle.

   Derived from the video
3. Expression

   $$\text{number of edges}=3$$
   Explanation

   A three-vertex cycle achieves strong connectivity using exactly three edges.

   Justification

   The presenter says, "In this case, it has the minimum number of edges."

   Shown in the video

The modified graph 2 is strongly connected and has the minimum number of edges in this example.

Check whether any two vertices can reach each other along a cycle.

1. Audio
   Observation

   "Let me draw it: letters A, B, C, D, E. We connect C to A, C to B, C to D, and C to E." "See? Four edges are used for five vertices."

2. Diagram
   Observation

   With a red pen, draw 5 points in the blank space and draw 4 edges centered at C.

Construct a connected undirected graph using 5 vertices and observe the minimum number of edges required.

1. vertices A, B, C, D, and E

2. require the graph to be connected

construct a connected graph with the minimum possible number of edges

1. Expression

   $$C-A,\ C-B,\ C-D,\ C-E$$
   Explanation

   take C as the central vertex and connect it to each of the other 4 vertices

   Justification

   then any two vertices can communicate via C, so the graph is connected

   Shown in the video
2. Expression

   $$4=5-1$$
   Explanation

   this construction uses exactly 4 edges

   Justification

   this matches the conclusion that a connected graph with n vertices requires at least n minus 1 edges

   Shown in the video

a connected undirected graph with 5 vertices requires at least 4 edges

the instructor directly counts the drawn edges as 4 and matches this with n minus 1

1. Audio
   Observation

   Is not the number of edges in a complete graph equal to n times n minus one, all over two? A is connected to each of the other four vertices… four plus three plus two plus one… equals five times four over two.

2. Formula
   Observation

   the board writes $4 + 3 + 2 + 1 = (5 \cdot 4) / 2$

3. Diagram
   Observation

   the left-side green complete graph on 5 vertices is circled and used for counting

Calculate how many edges a complete undirected graph with 5 vertices has.

1. Number of vertices $n = 5$

2. The graph is complete

Find the number of edges and relate it to the general formula $n(n - 1)/2$

1. Expression

   $$4+3+2+1$$
   Explanation

   Add edges sequentially by vertex order: the first vertex connects to 4 others, the second adds 3 more, the third adds 2 more, and the fourth adds 1 more.

   Justification

   Avoid double-counting the same undirected edge.

   Shown in the video
2. Expression

   $$\frac{5\cdot 4}{2}$$
   Explanation

   Write the above sum as the result of an arithmetic series sum.

   Justification

   The instructor verbally uses the phrase 'first term plus last term' for summation.

   Shown in the video
3. Expression

   $$\frac{n(n-1)}{2}\bigg|_{n=5}=\frac{5\cdot 4}{2}$$
   Explanation

   Substitute the general formula with $n = 5$ to obtain the same result.

   Justification

   Consistent with both the board work and oral explanation.

   Shown in the video

A complete graph with 5 vertices has 10 edges, namely ($5\cdot 4$)/2.

The special-case calculation matches the result from substituting into the general formula.

1. Audio
   Observation

   For example, suppose there are five vertices below: A, B, C, D, and E, plus another vertex F. To make this graph non-connected while having the maximum possible number of edges, we let these five vertices form a complete graph, and let F be disconnected from A, B, C, D, and E.

2. Diagram
   Observation

   A red pen circles vertices A, B, C, D, and E together, with F isolated outside.

1. The segment does not compute the exact number of edges for this example, stopping only at the construction description.

Construct an undirected graph that has as many edges as possible while remaining non-connected.

1. The example has 6 vertices: A, B, C, D, E, F

2. Require the graph to be non-connected

Explain how to maximize the number of edges while maintaining non-connectedness

1. Expression

   $$K_5 \text{ on } \{A,B,C,D,E\}$$
   Explanation

   Connect vertices A, B, C, D, and E pairwise to form a complete subgraph.

   Justification

   Among 5 vertices, the complete graph has the maximum number of edges.

   Shown in the video
2. Expression

   $$F \text{ isolated}$$
   Explanation

   Let F be disconnected from A, B, C, D, and E.

   Justification

   Thus, F itself forms an isolated component, and the entire graph remains disconnected.

   Shown in the video

This construction shows that the disconnected graph with the maximum number of edges can be obtained by taking a complete graph on n minus 1 vertices together with an isolated vertex.

The instructor directly supports the upper-bound reasoning through the construction of 'complete subgraph plus isolated vertex'.

1. Audio
   Observation

   The instructor says "because the total number of vertices is six" and "the final answer is five times four, all over two".

2. Animation
   Observation

   The instructor circles the number 6 in blank space and writes computational hints related to 5 and 4.

Given a total of 6 vertices, what is the maximum possible number of edges in an undirected disconnected graph?

1. Total number of vertices n equals 6

2. The graph is undirected

3. The graph is disconnected.

Find the maximum number of edges.

1. Expression

   $$\frac{(6-1)(6-2)}{2}$$
   Explanation

   Substitute into the formula for the maximum number of edges in a disconnected undirected graph.

   Justification

   Formula from the slide: |E| $\le \frac{(n-1)(n-2)}{2}$.

   Shown in the video
2. Expression

   $$\frac{5 \times 4}{2}$$
   Explanation

   Simplify the differences inside the parentheses.

   Justification

   The presenter says, "five halves times four."

   Shown in the video
3. Expression

   $$10$$
   Explanation

   Compute to obtain the maximum number of edges.

   Justification

   Arithmetic simplification.

   Derived from the video

10 edges.

Matches the general formula given on the slide when n equals 6.

1. Animation
   Observation

   The instructor writes 'undirected graph' next to 'connected graph' and 'directed graph' next to 'strongly connected graph'

2. Animation
   Observation

   The instructor draws a path A–C–D from A to D on the left undirected graph

3. Animation
   Observation

   The instructor draws bidirectional arrows between A and B on the right directed graph and writes '$A \to B$' and '$B \to A$' below

1. Undirected graph

2. Directed graph

3. Red handwritten script

1. Adding text labels to distinguish undirected and directed

2. Draw a path to illustrate connectivity.

3. Draw bidirectional arrows to illustrate strong connectivity.

1. The basic topological structure of the graph remains unchanged.

Use dynamic labeling to emphasize that connectivity applies to undirected graphs, while strong connectivity applies to directed graphs, and to visually demonstrate the concepts of paths and mutual reachability.

1. Diagram
   Observation

   The entire page title is "Connected Graphs and Strongly Connected Graphs"; the top-left shows an undirected graph example, the top-right shows a directed graph example, the bottom-left contains the text "Key Concept", and the bottom-right displays "Graph 1" and "Graph 2".

1. Main title: "Connected Graphs and Strongly Connected Graphs"

2. Left-side undirected graph example

3. Right-side directed graph example

4. Bottom-left key concept text

5. Bottom-right "Graph 1" and "Graph 2"

1. During the explanation, red arrows, circled annotations, and crosses are added sequentially to the right-side directed graph and to graphs 1 and 2 below.

1. The main page title and the two major definition areas on the left and right remain visible throughout.

The screen compares "connected" for undirected graphs and "strongly connected" for directed graphs, and tests these concepts using the example problem below.

1. Animation
   Observation

   The instructor traces paths along edges on the directed graph in the upper right and circles several vertices.

2. Audio
   Observation

   Simultaneously speaking: "A can go to B, then to C", "C can go to D, then to A", etc.

1. Vertices A, B, C, D, E

2. Directed edges

3. Red tracing path

1. Tracing several reachable paths sequentially along the arrows

2. Circling to emphasize the vertex pair currently under verification

1. The graph's structure remains unchanged

2. Arrow directions remain unchanged

Visual actions illustrate the pairwise verification process for "every pair of vertices is strongly connected".

1. Animation
   Observation

   The presenter traces the direction from A to D on Figure 1 and places a negation mark near D.

2. Audio
   Observation

   Simultaneously says, "D cannot go back to A."

1. Figure 1

2. Vertices A and D

3. Red mark

1. Emphasizes that $A\to D$ is reachable

2. Emphasizes that $D\to A$ is not reachable

1. Original edge directions in Figure 1 remain unchanged

Uses a pair of mutually unreachable vertices to show that Figure 1 is not strongly connected.

1. Animation
   Observation

   First points out on Figure 2 that $B\to A$ is reachable but $A\to B$ is not, then adds a reverse arrow to form a cycle.

2. Audio
   Observation

   The presenter first says, "Figure two is also not a strongly connected graph," then says, "Let us modify this arrow... to form a cycle; then it becomes a strongly connected graph."

1. Figure 2

2. Vertices A, B, and C

3. New red arrows

1. First mark that A cannot return to B

2. Then add arrows so that A, B, and C form a directed cycle

1. The vertex set remains unchanged

2. The object under discussion remains the same three-vertex directed graph

The same figure first serves as a counterexample to strong connectivity, then demonstrates a minimally strongly connected structure by reversing edge directions.

1. Diagram
   Observation

   The entire page is divided into left and right halves: the left half bears the title 'Connected Graph', and the right half bears the title 'Strongly Connected Graph'; below them appear the words 'Key Concept' and two small directed graph examples labeled 'Graph 1' and 'Graph 2'.

1. Left-side green undirected graph

2. Right-side orange directed graph

3. Key Concept text below

4. Graph 1 and Graph 2 in the lower-right corner

1. The left column always corresponds to undirected connected graphs

2. The right column always corresponds to directed strongly connected graphs

The page uses a side-by-side layout to contrast the concepts of connectivity and their extremal edge counts for undirected versus directed graphs.

1. Animation
   Observation

   A red pen writes A, B, C, D, and E sequentially in blank space, then draws edges from C to each of the other four points.

2. Audio
   Observation

   The presenter says in sync: 'C connects to A, C connects to B, C connects to D, C connects to E' and 'four edges are used for five vertices.'

1. Five red points labeled A, B, C, D, and E.

2. Four edges centered at C.

1. First, write the vertex labels.

2. Then draw edges one by one outward from the central vertex C.

1. The total number of vertices remains 5.

2. The number of edges ultimately becomes 4.

This animation demonstrates that a connected graph with n vertices can be realized using as few as n minus 1 edges.

1. Animation
   Observation

   A red pen circles the green complete graph on the left and writes above it 4, $4+3$, $4+3+2$, $4+3+2+1$, and finally ($5\cdot 4$)/2.

2. Formula
   Observation

   The boardwork progressively accumulates the sum and converts it into a product divided by 2.

1. Complete graph with 5 vertices on the left

2. Red summation expression $4+3+2+1$

3. Result ($5\cdot 4$)/2

1. First, circle the complete graph

2. Then, write out the summation term by term

3. Finally, rewrite it in product form

1. The number of vertices in the example is always 5

2. The object under discussion is always an undirected complete graph

The visual process converts the counting method of "adding edges point by point" into an arithmetic series sum, then transitions to the general formula $n(n-1)/2$.

1. Animation
   Observation

   Write A, B, C, D, E, F in red ink; circle A through E together, and leave F outside the circle.

2. Audio
   Observation

   The instructor says: make the five vertices into a complete graph, and keep F disconnected from all other vertices.

1. Six vertices labeled A, B, C, D, E, and F

2. Five enclosed vertices

3. Isolated vertex F

1. First list 6 vertices

2. Then enclose the first 5 vertices as one group

3. Finally leave F outside the group

1. Total number of vertices is 6

2. The graph remains disconnected throughout

This animation visually illustrates the extremal construction idea: 'one complete component plus one isolated vertex'.

1. Diagram
   Observation

   The entire frame shows a single slide: at the top left and right are examples labeled "connected graph" and "strongly connected graph", respectively; below them is the text "key concept" followed by a formula; in the bottom right corner are two small directed graph examples labeled "Figure 1" and "Figure 2".

1. Title: "Connected Graphs and Strongly Connected Graphs"

2. Left: example of a connected graph

3. Right: example of a strongly connected graph

4. Bottom: text and formula labeled "Key Concept"

5. Bottom right: "Graph 1", "Graph 2"

1. During explanation, red pen continuously adds circled annotations, letters, and arrows in blank areas

1. Main slide text and example diagrams remain constantly visible

2. The topic consistently focuses on extremal numbers of edges for connected and strongly connected graphs

The visual presentation is primarily static lecture notes, with dynamic red-pen annotations used to supplement derivations and construct examples.

1. Animation
   Observation

   The instructor circles "6" in blank space and successively writes n, $n-1$, $n-2$, etc., annotating the maximum number of edges in a disconnected graph.

1. Some handwritten symbols are messy, but audio confirms they illustrate relationships among n, $n-1$, and $n-2$.

1. the circled number 6

2. handwritten n, $n-1$, $n-2$

3. original slide formula

1. transition from the specific value 6 to the general expressions $n-1$ and $n-2$

2. highlighting the idea that "the remaining vertices form a complete graph" through circling

1. the original slide formula remains unchanged

these annotations connect the abstract formula $\frac{(n−1)(n−2)}{2}$ with the construction of "removing one isolated vertex and fully connecting the rest".

1. Animation
   Observation

   the presenter draws four vertices A, B, C, D and directed arrows on blank space, forming a cyclic structure.

2. Audio
   Observation

   the presenter says aloud, "let it become a cycle" and "n vertices correspond to n edges".

1. the spoken order of arrows does not exactly match the local handwriting sequence in the video, but both point to the same directed cycle construction.

1. handwritten vertices A, B, C, D

2. directed arrow

3. blank annotation area

1. first write the vertex letter, then add the directed edge, and finally form a cycle

1. when the number of vertices is 4, the number of edges is also 4

2. the purpose of construction is to illustrate the minimum-edge case

this animation visually demonstrates how the minimum number of edges n for a strongly connected directed graph is achieved: by arranging all vertices into a single directed cycle.

1. Audio
   Observation

   Some students think that since there is no red edge directly connecting A and D, A and D are not connected. This understanding is clearly incorrect.

Believing that two vertices must be joined by a direct edge to be connected.

Connectivity means there exists a path between two vertices; the path may pass through other intermediate vertices and does not require a direct connection.

1. Audio
   Observation

   The instructor repeatedly emphasizes 'D cannot go back to A' and 'How can A reach B? Impossible.'

2. Diagram
   Observation

   Both Figure 1 and Figure 2 rely on arrow direction to determine reachability.

Assuming two vertices are strongly connected just because there is a path between them.

Strong connectivity requires mutual reachability; satisfying reachability in only one direction is insufficient to conclude strong connectivity.

1. Audio
   Observation

   The instructor asks, 'When is the situation minimal? It is when it resembles a tree.'

2. Formula
   Observation

   The board writes that a connected undirected graph has at least $n-1$ edges.

Thinking that connectivity alone requires nearly as many edges as a complete graph.

A connected undirected graph with n vertices needs only $n-1$ edges at minimum, with the tree structure being a typical example.

1. Caption evidence
   Observation

   If the graph is disconnected, then z can have at most ($n-1$)×($n-2$)/2 edges.

1. It is unclear whether z is a typographical error or a typesetting placeholder; its definition is not provided within the fragment.

Readers might mistakenly think z is another newly introduced quantity.

In the context of this segment, the sentence actually states that a disconnected graph can have at most (n-1)(n-2)/2 edges; z is not otherwise defined and should be regarded as a suspicious typesetting error or typo, not a new mathematical object.

1. Diagram
   Observation

   The left column 'connected graph' pairs with an undirected graph; the right column 'strongly connected graph' pairs with a directed graph.

2. Caption evidence
   Observation

   The definitions on both sides respectively emphasize 'any two vertices are connected' and 'any pair of vertices is strongly connected'.

Might treat 'connected graph' and 'strongly connected graph' as the same condition.

This segment clearly distinguishes the two via side-by-side columns: a connected graph applies to undirected graphs and only requires that any two vertices be connected; a strongly connected graph applies to directed graphs and requires that any pair of vertices be mutually reachable.

1. Caption evidence
   Observation

   An undirected connected graph has at least n-1 edges; a directed strongly connected graph has at least n edges (a cycle).

2. Diagram
   Observation

   The example on the right is a directed cycle.

Might mistakenly assume the minimum number of edges is the same for undirected connected graphs and directed strongly connected graphs.

The segment explicitly gives different lower bounds: an undirected connected graph has at least n minus 1 edges, whereas a directed strongly connected graph has at least n edges, because directed cycles are needed in directed graphs to ensure mutual reachability.

1. Diagram
   Observation

   the "connected graph" example on the left does not have a direct edge between every pair of vertices, but rather connects every pair via a path.

2. Formula
   Observation

   the slide simultaneously gives the minimum number of edges for a connected graph as n minus 1, and the maximum number as $\frac{n(n-1)}{2}$.

it is easy to mistakenly think that in a connected graph, every pair of vertices must be joined by a direct edge.

the definition given in the video is "any two vertices are connected", meaning a path exists; only when the maximum number of edges $\frac{n(n-1)}{2}$ is reached does it become an undirected complete graph.

1. Audio
   Observation

   the instructor emphasizes "if this isolated vertex has an edge to any one of the five vertices below, then it cannot be a disconnected graph."

When finding the maximum number of edges in a disconnected graph, one might mistakenly think of connecting an isolated vertex to all other vertices to increase the edge count.

The video explains that once this single vertex connects to any other vertex, the graph is no longer disconnected; thus, the maximum number of edges must come solely from the complete connection among the remaining $n-1$ vertices.

1. Audio
   Observation

   The presenter uses a 'cycle' to illustrate the minimum number of edges and states, 'n vertices correspond to n edges.'

One easily conflates 'strong connectivity' directly with 'having many edges.'

The video gives the minimal case: just a directed cycle, requiring only n edges for strong connectivity among n vertices.

1. Audio
   Observation

   This definition is quite similar to the one used for connected graphs, isn’t it?

A connected graph applies to undirected graphs and requires a path between any two vertices; a strongly connected graph applies to directed graphs and requires a bidirectional path between any two vertices. Although their definitions have similar forms, they apply to different types of graphs and impose different conditions.

1. Formula
   Observation

   Definitions for 'connected graph' and 'strongly connected graph' appear on the left and right sides respectively.

2. Diagram
   Observation

   The left side pairs with an undirected graph; the right side pairs with a directed graph.

A connected graph applies to undirected graphs where any two vertices are reachable; a strongly connected graph applies to directed graphs where any two vertices are mutually reachable.

1. Audio
   Observation

   The instructor first says that after changing to a cycle, 'the number of edges is minimal,' then later writes on the board that a strongly connected directed graph has at least n edges.

Earlier, a three-vertex cycle was used intuitively to illustrate the minimal strongly connected structure; later, this was generalized to state that a directed strongly connected graph with n vertices has at least n edges.

1. Formula
   Observation

   The board writing in 'Key Points' directly states that for 'G is a connected graph', the minimum number of edges is n minus 1, and the maximum number is n times (n minus 1) divided by 2.

The definition of a connected graph is used to derive the extremal numbers of edges for undirected graphs in both connected and disconnected cases.

1. Caption evidence
   Observation

   First gives the definition of 'connected graph', then states in the 'key point' section: 'If G is a connected graph, then it has at least n minus 1 edges.'

The definition of a connected graph directly leads to its minimum edge count: to ensure connectivity between any two vertices, at least n minus 1 edges are required.

1. Audio
   Observation

   The instructor explains the maximum number of edges as 'In a complete graph, isn't it n times n minus one, divided by two?'

The maximum number of edges in an undirected graph corresponds to the complete graph; in contrast, the maximum number of edges in a disconnected graph arises from the constructive comparison: 'remove one isolated vertex, and make the remaining n minus 1 vertices as dense as possible.'

1. Caption evidence
   Observation

   The right column first defines 'strongly connected graph'; later it states: 'If G is a strongly connected graph, then it has at least n edges (a cycle).'

The mutual reachability requirement of strong connectivity directly corresponds to directed cycles—the minimal realization requiring exactly n edges.

1. Diagram
   Observation

   The left column shows an undirected graph example; the right column shows a directed graph example; their headings are 'Connected Graph' and 'Strongly Connected Graph', respectively.

The segment juxtaposes undirected graph connectivity with directed graph strong connectivity, emphasizing differences in applicable objects and criteria for determination.

1. Formula
   Observation

   The slide first defines a connected graph, then states, 'If G is a connected graph, it has at least $n-1$ edges and at most $n\times (n-1)$∕2.'

The edge-number range for undirected connected graphs is built directly upon the definition of 'connected graph.'

1. Formula
   Observation

   The slide first defines a strongly connected graph, then states, 'In a directed graph G with n vertices, if G is strongly connected, it has at least n edges … and at most $n\times (n-1)$.'

The extremal edge-number statement for directed strongly connected graphs takes the definition of 'strongly connected graph' as its premise.

1. Audio
   Observation

   The presenter says, 'This maximum case matches the property we discussed earlier: the maximum is n times (n minus one) over two,' and adds, 'Because in a directed graph, each undirected edge corresponds to two directed edges, so we multiply by two.'

The video compares the maximum number of edges in a directed graph, $n(n-1)$, with that in an undirected complete graph, $\frac{n(n−1)}{2}$, to illustrate that each pair of vertices in the directed case can have two opposite-directed edges.

1. Formula
   Observation

   The slide lists side by side: "If G is a connected graph..." and "If it is a disconnected graph...".

Undirected graphs of the same type are divided into two extremal edge-number cases based on whether they are connected.

1. Audio
   Observation

   Alright, let’s now look at the definition of a connected graph.

1. definition of a connected graph

1. Audio
   Observation

   In a strongly connected graph, any pair of vertices is strongly connected; such a graph is called strongly connected.

1. Definition of a strongly connected graph

1. Caption evidence
   Observation

   Key point: For an undirected graph G with N vertices...

1. Range of number of edges in a connected graph
2. maximum number of edges in a disconnected graph

1. Formula
   Observation

   The text on the right directly gives the definition of a strongly connected graph.

1. Strongly connected graph

1. Audio
   Observation

   The instructor uses the path from A to D and the inability to return from D to A to determine whether graph 1 is strongly connected.

1. Strongly connected graph
2. Is Graph 1 strongly connected?

1. Audio
   Observation

   The instructor says that after changing it into a cycle, 'the number of edges is minimal.'

2. Formula
   Observation

   The board writing states that a directed strongly connected graph has a minimum of n edges.

1. Number of edges in directed strongly connected graphs
2. Modify graph 2 to make it strongly connected

1. Formula
   Observation

   The board writing lists the edge-count formulas for undirected connected and disconnected graphs.

1. Number of edges in undirected connected versus disconnected graphs

1. Caption evidence
   Observation

   If every pair of vertices in a graph is connected, the graph is called a connected graph; otherwise, it is disconnected.

1. Connected graphs and disconnected graphs

1. Caption evidence
   Observation

   If every ordered pair of vertices in a graph is strongly connected, then the graph is called a strongly connected graph.

1. strongly connected graph