Introduction to Planar Graphs and Euler's Formula

1. Formula
   Observation

   The slide text introduces “the number of vertices (v)”.

2. Audio
   Observation

   The narrator says, “And there is a connection between the number of vertices v …”.

v

number of vertices in a connected planar graph

nonnegative integer count of graph vertices

1. Formula
   Observation

   The slide text introduces “the number of edges (e)”.

2. Audio
   Observation

   The narrator begins, “the number of edges e …” before the clip ends.

e

number of edges in a connected planar graph

nonnegative integer count of graph edges

1. Formula
   Observation

   The slide states “f faces” in Euler’s formula line.

2. Audio
   Observation

   The narration repeatedly discusses counting faces and later introduces the connection involving faces.

f

number of faces in a connected planar graph drawn without edge crossings

positive integer count of regions including the outside region

1. Caption evidence
   Observation

   The slide text names the number of vertices as v.

2. Audio
   Observation

   The lecturer says “with v vertices.”

v

Number of vertices in a connected planar graph.

Nonnegative integer; in the worked base case shown on the slide, $v = 2$.

1. Caption evidence
   Observation

   The slide text names the number of edges as e.

2. Audio
   Observation

   The lecturer says “e edges.”

e

Number of edges in a connected planar graph.

Nonnegative integer; in the worked base case shown on the slide, $e = 1$.

1. Caption evidence
   Observation

   The slide text names the number of faces as f.

2. Audio
   Observation

   The lecturer says “f faces.”

f

Number of faces in a connected planar graph, including the outside face when counted in the planar representation.

Positive integer in the examples shown; in the worked base case on the slide, $f = 1$.

1. Caption evidence
   Observation

   The slide states “Start with the graph $P_2$.”

2. Diagram
   Observation

   A two-vertex one-edge graph is drawn as the starting example.

$P_2$

The path graph used as the starting graph for the inductive argument.

A specific connected graph with 2 vertices and 1 edge.

1. Caption evidence
   Observation

   The slide states “The smallest graph where this happens is $K_5$.”

2. Diagram
   Observation

   A five-vertex complete graph is drawn at the bottom right.

$K_5$

The complete graph on 5 vertices, used as the smallest non-planar example in this segment.

A specific graph with 5 vertices and all possible edges between them.

1. Formula
   Observation

   The variable v appears in the expression $v - e + f$ and is defined as the number of vertices.

v

Number of vertices in a graph

Positive integer

1. Formula
   Observation

   The variable e appears in the expression $v - e + f$ and is defined as the number of edges.

e

Number of edges in a graph

Positive integer

1. Formula
   Observation

   The variable f appears in the expression $v - e + f$ and is defined as the number of faces.

f

Number of faces in a planar graph

Positive integer

1. Formula
   Observation

   The notation $P_2$ is used to denote the starting graph with 2 vertices and 1 edge.

$P_2$

A path graph with 2 vertices

Graph

1. Audio
   Observation

   Narrator: “When a connected graph can be drawn without any edges crossing, it is called planar.”

2. Formula
   Observation

   Slide definition box: “A planar graph is a connected graph that can be drawn without any edges crossing.”

A planar graph is defined as a connected graph that admits at least one drawing in the plane with no edge crossings. The key point is existence of some crossing-free representation, not that every drawing must look crossing-free.

1. The graph is connected.

2. Planarity means there exists a drawing without any edges crossing.

1. Audio
   Observation

   Narrator: “When a planar graph is drawn in this way, it divides the plane into regions called faces.”

2. Formula
   Observation

   Slide text: “it divides the plane into regions called faces.”

3. Diagram
   Observation

   The right-hand graph is annotated with face labels 1, 2, and 3.

When a planar graph is drawn without edge crossings, its edges and vertices partition the plane into regions called faces. The outside unbounded region is also counted as a face.

1. The graph must be drawn in a planar way, i.e. without edge crossings.

2. Faces are the resulting regions of the plane, including the outside region.

1. Definition of a planar graph

1. Audio
   Observation

   Narrator: “Even if a graph does not look like it is planar, it still might be. Perhaps we can redraw it in a way in which no edges cross.”

2. Diagram
   Observation

   A left graph with crossings is shown transforming into a right graph without crossings.

3. Formula
   Observation

   Slide text: “the original drawing of the graph was not a planar representation of the graph.”

A graph may have drawings with crossings and still be planar if another drawing of the same graph has no crossings. A drawing with crossings is not a planar representation, even though the underlying graph may be planar.

1. Applies to the same graph considered under different drawings.

2. Only a crossing-free drawing counts as a planar representation.

1. Definition of a planar graph

1. Audio
   Observation

   Narrator: “The number of faces does not change no matter how we draw the graph, as long as we do so without the edges crossing.”

2. Formula
   Observation

   Slide text repeats that the number of faces does not change for planar drawings.

For a given planar graph, the number of faces is treated as invariant across different planar drawings. This justifies speaking of the number of faces as a property of the planar graph rather than of one particular picture.

1. The graph is planar.

2. The comparison is only among drawings without edge crossings.

1. Faces of a planar embedding
2. Planar representation versus nonplanar drawing

1. Formula
   Observation

   Slide text: “Euler’s Formula for Planar Graphs. For any (connected) planar graph with v vertices, e edges and f faces, we have: $v - e + f = 2$”

2. Audio
   Observation

   Narrator begins introducing the connection among vertices, edges, and faces just before the clip ends.

1. The spoken explanation of the formula is cut off before completion; only the displayed formula is fully visible.

For any connected planar graph, the numbers of vertices, edges, and faces satisfy Euler’s relation. The slide presents the formula explicitly as a central relationship among these three quantities.

1. The graph is connected.

2. The graph is planar.

3. f is counted from a planar drawing, including the outside face.

1. Definition of a planar graph
2. Faces of a planar embedding
3. v
4. e
5. f

1. Caption evidence
   Observation

   The slide warns: “We can only count faces when the graph is drawn in a planar way.”

2. Diagram
   Observation

   Two representations of the same graph are shown side by side, one non-planar-looking and one planar with labeled faces 1, 2, 3, 4.

This segment defines the counting rule implicitly by warning that face counts are valid only after the graph is drawn without edge crossings. The left drawing may suggest 5 faces including the outside, but the planar representation on the right shows there are only 4 faces.

1. The graph must be drawn in a planar way before faces are counted.

2. The outside region is included among the faces in the discussion.

1. Caption evidence
   Observation

   The slide states: “For any (connected) planar graph with v vertices, e edges and f faces, we have: $v - e + f = 2$.”

2. Audio
   Observation

   The lecturer reads the formula aloud as “v minus e plus f equals 2.”

Euler's formula relates the numbers of vertices, edges, and faces of a connected planar graph through the invariant equation $v - e + f = 2$.

1. The graph is planar.

2. The graph is connected.

3. v, e, and f are counted for a planar representation.

1. Faces must be counted from a planar drawing

1. Caption evidence
   Observation

   The slide says: “One way to convince ourselves of its validity is to draw a planar graph step by step. Start with the graph $P_2$.”

2. Caption evidence
   Observation

   The slide says each step consists of either adding a spike or connecting two existing vertices with a new edge.

3. Audio
   Observation

   The lecturer explains building up the graph by adding edges and vertices using these two moves.

The segment presents an inductive construction method: start from $P_2$ and repeatedly apply two allowed operations, called a spike and a circuit-closing edge, to build any connected graph besides a single isolated vertex.

1. The starting graph is $P_2$.

2. Each step adds either one new vertex with one new edge, or one new edge between two existing vertices.

3. The argument applies to connected graphs other than a single isolated vertex.

1. Euler's formula for connected planar graphs

1. Caption evidence
   Observation

   The slide labels the left move: “Adding a new vertex connected by a new edge. (spike)”

2. Audio
   Observation

   The lecturer calls this move a spike and says it is an edge and a vertex.

A spike is the operation of adding one new vertex together with one new edge connecting it to the existing graph.

1. It is applied during the step-by-step construction of a connected planar graph.

1. Proof method: build any connected planar graph from $P_2$ by two moves

1. Caption evidence
   Observation

   The slide labels the right move: “Connecting two vertices in the graph.”

2. Caption evidence
   Observation

   The surrounding text says this move is “(completing a circuit).”

3. Audio
   Observation

   The lecturer describes connecting two existing vertices with a new edge.

The second allowed operation adds one new edge between two vertices already present in the graph, thereby completing a circuit.

1. Both endpoints already exist in the graph.

2. The move is used in the inductive construction argument.

1. Proof method: build any connected planar graph from $P_2$ by two moves

1. Caption evidence
   Observation

   The slide states: “Not all graphs are planar. If there are too many edges and too few vertices, then some of the edges will need to intersect. The smallest graph where this happens is $K_5$.”

2. Diagram
   Observation

   A drawing of $K_5$ is shown at the bottom right.

The segment contrasts planar graphs with non-planar ones, explaining that when a graph has too many edges relative to its vertices, some edges must cross. It identifies $K_5$ as the smallest example where this occurs.

1. The statement concerns graphs that cannot be drawn without edge intersections.

2. $K_5$ is presented as the smallest such example in this segment.

1. Faces must be counted from a planar drawing

1. Audio
   Observation

   Speaker states that adding a spike or completing a circuit does not change the quantity $v - e + f$.

2. Formula
   Observation

   Text on screen shows '$v - e + f$ does not change' for both operations.

Adding a new vertex connected by a new edge (spike) increases both vertices and edges by 1, leaving $v - e + f$ unchanged. Connecting two existing vertices (circuit) increases edges and faces by 1, also leaving $v - e + f$ unchanged.

1. Graph must be planar

2. Operations must maintain planarity

1. v
2. e
3. f

1. Audio
   Observation

   Narrator: “The two graphs are the same, so if one is planar, the other must be too.”

2. Diagram
   Observation

   Two drawings are presented as representations of the same graph.

If two drawings represent the same graph and one drawing is planar, then the graph is planar, so another drawing of the same graph may also be planar even if it visually contains crossings.

1. The two drawings represent the same graph.

For the same graph under different drawings.

1. Audio
   Observation

   Narrator: “We can only count faces when the graph is drawn in a planar way.”

2. Formula
   Observation

   Slide warning text: “WARNING: We can only count faces when the graph is drawn in a planar way.”

The number of faces should be determined from a planar representation of the graph, not from a drawing with edge crossings.

1. The graph is being analyzed for its face count.

For any graph whose faces are being counted.

1. Formula
   Observation

   Slide text: “For any (connected) planar graph with v vertices, e edges and f faces, we have: $v - e + f = 2$”

1. The narrator does not finish explaining the formula within this clip.

For any connected planar graph with v vertices, e edges, and f faces, $v - e + f = 2$.

1. The graph is connected.

2. The graph is planar.

3. f is the number of faces in a planar drawing, including the outside face.

For all connected planar graphs.

1. Caption evidence
   Observation

   The slide explicitly states the theorem for any connected planar graph with v vertices, e edges, and f faces.

2. Audio
   Observation

   The lecturer repeats that the formula holds for all connected planar graphs.

For any connected planar graph with v vertices, e edges, and f faces, $v - e + f = 2$.

1. The graph is planar.

2. The graph is connected.

3. Faces are counted in a planar representation.

For all connected planar graphs.

1. Caption evidence
   Observation

   The slide states: “Any connected graph (besides just a single isolated vertex) must contain this subgraph.”

2. Audio
   Observation

   The lecturer says any connected graph besides a single isolated vertex must contain this subgraph.

Any connected graph besides a single isolated vertex must contain $P_2$ as a subgraph.

1. The graph is connected.

2. The graph is not just a single isolated vertex.

For all connected graphs except the one-vertex isolated case.

1. Caption evidence
   Observation

   The slide states that when adding the spike, edges increase by 1, vertices increase by 1, faces remain the same, so $v - e + f$ does not change.

2. Audio
   Observation

   The lecturer explains that because v and e both increase by 1, the quantity $v - e + f$ stays the same.

Adding a spike increases v by 1 and e by 1 while leaving f unchanged, so the quantity $v - e + f$ does not change.

1. The move is the spike operation defined in the segment.

For each application of the spike move.

1. Caption evidence
   Observation

   The slide states that completing a circuit adds one edge, adds one face, and keeps the number of vertices the same, so again $v - e + f$ does not change.

2. Audio
   Observation

   The lecturer says increasing edges by 1 and faces by 1 leaves $v - e + f$ unchanged because -1 + $1 = 0$.

Completing a circuit increases e by 1 and f by 1 while leaving v unchanged, so the quantity $v - e + f$ does not change.

1. The move connects two existing vertices with a new edge in the planar construction.

For each application of the circuit-completing move.

1. Caption evidence
   Observation

   The slide states: “our starting graph $P_2$ has $v = 2$, $e = 1$ and $f = 1$, so $v - e + f = 2$.”

1. The slide gives $f = 1$ for $P_2$ without further explanation of how the outside face is being counted in that base case.

For the starting graph $P_2$, $v = 2$, $e = 1$, and $f = 1$, hence $v - e + f = 2$.

1. The graph is the specific starting graph $P_2$ used in the construction argument.

For the base graph $P_2$.

1. Caption evidence
   Observation

   The slide states: “The smallest graph where this happens is $K_5$.”

2. Diagram
   Observation

   A drawing of $K_5$ accompanies the statement.

1. The segment asserts minimality but does not prove why no smaller graph is non-planar.

Among the graphs discussed here, the smallest graph that necessarily requires edge intersections is $K_5$.

1. The graph has too many edges relative to its vertices to be drawn without intersections.

Stated for the smallest example in this segment.

1. Audio
   Observation

   Speaker concludes that since any graph can be built using these moves which preserve $v - e + f$, the quantity is the same for all graphs.

2. Formula
   Observation

   Text states 'that quantity will be the same for all graphs'.

1. Video does not explicitly state the final theorem name 'Euler's Formula' in the audio, though it is implied by the context and title.

For any connected planar graph, the quantity $v - e + f$ equals 2.

1. Graph is planar

2. Graph is connected

For all connected planar graphs

1. Audio
   Observation

   Narrator explains that the graph above has three faces, including the outside region.

2. Diagram
   Observation

   The right-hand planar drawing is labeled with regions 1, 2, and 3.

1. Expression

   $$$$
   Explanation

   Start from the planar drawing on the right, where no edges cross.

   Justification

   Faces are counted only after choosing a planar representation.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Identify the bounded regions created by the edges and vertices; the picture marks two inner regions.

   Justification

   By definition, a planar drawing divides the plane into regions called faces.

   Shown in the video
3. Expression

   $$$$
   Explanation

   Include the unbounded outside region as a third face.

   Justification

   The video explicitly states that the outside region is counted as a face.

   Shown in the video
4. Expression

   $$2+1=3$$
   Explanation

   Therefore the graph has three faces in total.

   Justification

   Sum of two inner faces and one outer face.

   Derived from the video

The first example graph has 3 faces when drawn planarly.

1. Audio
   Observation

   Narrator contrasts an incorrect count of 5 faces from the crossing drawing with the correct count of 4 faces from the planar drawing.

2. Diagram
   Observation

   Left graph has crossing diagonals; right graph is redrawn without crossings and labeled 1, 2, 3, 4.

1. Expression

   $$$$
   Explanation

   If one uses the left drawing with crossing diagonals, it visually appears to create four inner regions plus the outside, suggesting 5 faces.

   Justification

   This is the mistaken count discussed in the video.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Redraw the same graph in a planar way, as shown on the right.

   Justification

   Face counting is valid only for a planar representation.

   Shown in the video
3. Expression

   $$$$
   Explanation

   In the planar drawing, identify three inner regions and one outside region.

   Justification

   The right-hand diagram is labeled with regions 1, 2, 3, and 4.

   Shown in the video
4. Expression

   $$3+1=4$$
   Explanation

   Hence the correct number of faces is 4.

   Justification

   Sum of three inner faces and one outer face.

   Derived from the video

The same graph has only 4 faces when counted from a planar representation, not 5.

1. Caption evidence
   Observation

   The slide lays out the construction from $P_2$, the two moves, their effects on v, e, f, and the base-case computation.

2. Audio
   Observation

   The lecturer narrates the same sequence: start from $P_2$, add spikes or close circuits, observe that $v - e + f$ never changes, and conclude by induction.

1. The final sentence in the audio is cut off mid-thought, but the visible slide already states the inductive conclusion.

1. Expression

   $$P_2$$
   Explanation

   Begin with the graph $P_2$, which has two vertices connected by one edge.

   Justification

   The slide explicitly says to start with the graph $P_2$.

   Shown in the video
2. Expression

   $$v=2,\ e=1,\ f=1$$
   Explanation

   Record the initial counts for the base graph.

   Justification

   These values are stated directly on the slide.

   Shown in the video
3. Expression

   $$v-e+f=2$$
   Explanation

   Compute the invariant for the base case: $2 - 1 + 1 = 2$.

   Justification

   This is the arithmetic shown on the slide for $P_2$.

   Shown in the video
4. Expression

   $$\text{spike: } v\mapsto v+1,\ e\mapsto e+1,\ f\mapsto f$$
   Explanation

   When a spike is added, one vertex and one edge are added, while the number of faces stays the same.

   Justification

   The slide states that adding the spike increases edges by 1, vertices by 1, and leaves faces unchanged.

   Shown in the video
5. Expression

   $$(v+1)-(e+1)+f=v-e+f$$
   Explanation

   Therefore the quantity $v - e + f$ is unchanged by a spike.

   Justification

   The slide says this means $v - e + f$ does not change; the algebraic form is an explicit restatement of that claim.

   Derived from the video
6. Expression

   $$\text{circuit: } v\mapsto v,\ e\mapsto e+1,\ f\mapsto f+1$$
   Explanation

   When a circuit is completed by joining two existing vertices with a new edge, one edge and one face are added, while the number of vertices stays the same.

   Justification

   The slide states that completing a circuit adds one edge, adds one face, and keeps vertices the same.

   Shown in the video
7. Expression

   $$v-(e+1)+(f+1)=v-e+f$$
   Explanation

   Therefore the quantity $v - e + f$ is also unchanged by completing a circuit.

   Justification

   The slide says again $v - e + f$ does not change; the displayed algebra makes that invariance explicit.

   Derived from the video
8. Expression

   $$\text{any connected graph (except one isolated vertex) can be built from }P_2\text{ by these moves}$$
   Explanation

   Since every nontrivial connected graph contains $P_2$ and can be built up using spikes and circuit-closing edges, the invariant value established for $P_2$ carries over to the whole graph.

   Justification

   The slide states that any connected graph besides a single isolated vertex must contain this subgraph and that we can build any graph using a combination of these two moves.

   Shown in the video
9. Expression

   $$v-e+f=2\ \text{for all connected planar graphs}$$
   Explanation

   Because the moves never change $v - e + f$ and the base case equals 2, the formula holds for every connected planar graph reached by this construction.

   Justification

   The slide concludes that this argument is essentially a proof by induction.

   Shown in the video

Euler's formula $v - e + f = 2$ follows by starting from $P_2$ and showing that both allowed construction moves preserve the quantity $v - e + f$.

1. Caption evidence
   Observation

   The slide contrasts a misleading count of 5 faces on the left with the correct planar count of 4 faces on the right.

2. Diagram
   Observation

   The right-hand planar drawing labels four regions 1, 2, 3, 4.

1. Expression

   $$\text{left drawing: apparent count }5$$
   Explanation

   If one tries to count faces from the non-planar-looking drawing on the left, one might say there are 5 faces including the outside.

   Justification

   This is stated directly in the slide text.

   Shown in the video
2. Expression

   $$\text{right drawing: planar count }4$$
   Explanation

   Redrawing the same graph in a planar representation shows that there are actually only 4 faces.

   Justification

   The slide text and the labeled planar diagram both state this.

   Shown in the video

Face counting depends on using a planar representation; otherwise the same graph can be miscounted.

1. Audio
   Observation

   Speaker explains building any graph from $P_2$ using spikes and circuits, noting this argument is essentially a proof by induction.

2. Formula
   Observation

   Text describes the two moves and their effect on v, e, f.

1. Expression

   $$v \to v+1, e \to e+1, f \to f$$
   Explanation

   Adding a spike increases vertices and edges by 1, faces remain constant.

   Justification

   Definition of spike operation shown in diagram.

   Shown in the video
2. Expression

   $$(v+1) - (e+1) + f = v - e + f$$
   Explanation

   The change in the quantity is zero for a spike.

   Justification

   Algebraic simplification.

   Derived from the video
3. Expression

   $$v \to v, e \to e+1, f \to f+1$$
   Explanation

   Completing a circuit increases edges and faces by 1, vertices remain constant.

   Justification

   Definition of circuit operation shown in diagram.

   Shown in the video
4. Expression

   $$v - (e+1) + (f+1) = v - e + f$$
   Explanation

   The change in the quantity is zero for a circuit.

   Justification

   Algebraic simplification.

   Derived from the video
5. Expression

   $$v=2, e=1, f=1 \implies v-e+f=2$$
   Explanation

   Base case $P_2$ satisfies the formula.

   Justification

   Direct calculation from definition of $P_2$.

   Shown in the video

Since the base case holds and the operations preserve the value, $v - e + f = 2$ for all connected planar graphs constructible via these operations.

1. Diagram
   Observation

   A left graph with crossings is transformed into a right graph without crossings.

2. Audio
   Observation

   Narrator says the lower graph is planar because it can be redrawn as the graph on the right.

3. Caption evidence
   Observation

   Pop-up notice: “Both graphs have 5 vertices and the degrees of the vertices are the same. You may want to pause the video and check this.”

1. The exact adjacency list is not written out on screen; only the drawings and the notice about equal vertex degrees are explicit.

Determine whether a graph that is initially drawn with edge crossings can still be planar, and count its faces once redrawn planarly.

1. A graph is shown on the left with crossing edges.

2. The same graph is redrawn on the right without crossings.

3. The pop-up notice states both graphs have 5 vertices and matching vertex degrees.

Show that the graph is planar and determine the number of faces in the planar drawing.

1. Expression

   $$$$
   Explanation

   Observe that the left drawing contains crossings, so it is not itself a planar representation.

   Justification

   A planar representation requires no edge crossings.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Use the right drawing, which has no crossings, as a planar representation of the same graph.

   Justification

   The video states the two graphs are the same and the right one is a redrawn version.

   Shown in the video
3. Expression

   $$$$
   Explanation

   Count the regions in the right drawing: two inner regions and one outside region.

   Justification

   Faces are the regions formed by a planar drawing, and the outside region is included.

   Shown in the video
4. Expression

   $$f=3$$
   Explanation

   Thus the graph has 3 faces.

   Justification

   2 inner faces + 1 outer face = 3 faces.

   Derived from the video

The graph is planar, and its planar drawing has 3 faces.

The visual labeling of regions 1, 2, and 3 on the right-hand drawing matches the narrated count.

1. Formula
   Observation

   Slide warning text states that faces can only be counted when the graph is drawn in a planar way.

2. Diagram
   Observation

   Two representations of the same graph are shown: one with crossing diagonals and one planar.

3. Audio
   Observation

   Narrator contrasts an apparent count of 5 faces with the correct count of 4 faces.

1. The exact edge count is not spoken aloud in this clip, although it is visible from the drawing.

Compare two drawings of the same graph and determine the correct number of faces.

1. The left drawing has crossing diagonals.

2. The right drawing is a planar representation of the same graph.

3. The right drawing is labeled with four regions.

Explain why the left drawing suggests 5 faces while the correct face count is 4.

1. Expression

   $$$$
   Explanation

   From the left drawing, one might mistakenly count four inner regions plus the outside, giving 5.

   Justification

   This is the erroneous method explicitly warned against in the video.

   Shown in the video
2. Expression

   $$$$
   Explanation

   Switch to the right drawing, which has no crossings.

   Justification

   Only a planar representation gives the valid face count.

   Shown in the video
3. Expression

   $$$$
   Explanation

   Count three inner regions and one outside region in the right drawing.

   Justification

   The diagram labels regions 1, 2, 3, and 4.

   Shown in the video
4. Expression

   $$f=4$$
   Explanation

   Therefore the correct number of faces is 4.

   Justification

   3 inner faces + 1 outer face = 4 faces.

   Derived from the video

The graph has 4 faces, not 5.

The slide text and narration both state that the planar representation shows only 4 faces.

1. Diagram
   Observation

   Two drawings of the same graph are shown side by side; the right one is planar and labels four faces 1, 2, 3, 4.

2. Caption evidence
   Observation

   The text says the left drawing might suggest 5 faces including the outside, but the planar representation shows only 4 faces.

1. The graph itself is not named in the visible text, though the drawing corresponds to $K_4$.

Compare two representations of the same graph and determine how many faces should be counted.

1. Two drawings of the same graph are shown.

2. The left drawing has crossing edges.

3. The right drawing is a planar representation with regions labeled 1, 2, 3, 4.

Identify the correct face count for the graph.

1. Expression

   $$\text{Left drawing: possibly }5\text{ faces including the outside}$$
   Explanation

   Using the left drawing naively may lead to counting 5 faces.

   Justification

   The slide explicitly says one might say there are 5 faces including the outside.

   Shown in the video
2. Expression

   $$\text{Right drawing: }4\text{ faces}$$
   Explanation

   Using the planar representation shows the correct count is 4 faces.

   Justification

   The slide states that the planar representation shows there are only 4 faces.

   Shown in the video

The correct face count in the planar representation is 4.

The labeled planar drawing on the right shows exactly four numbered regions, matching the slide's stated correction.

1. Caption evidence
   Observation

   The slide states: “our starting graph $P_2$ has $v = 2$, $e = 1$ and $f = 1$, so $v - e + f = 2$.”

2. Diagram
   Observation

   A two-vertex one-edge graph is shown as the starting example.

1. The segment does not explain in detail why $f = 1$ for $P_2$ beyond stating it on the slide.

Compute $v - e + f$ for the starting graph $P_2$ used in the proof.

1. The starting graph is $P_2$.

2. It has 2 vertices and 1 edge.

3. The slide assigns $f = 1$ for this base case.

Verify the invariant value at the start of the induction.

1. Expression

   $$v=2,\ e=1,\ f=1$$
   Explanation

   Read off the counts for the base graph from the slide.

   Justification

   These values are explicitly stated on the slide.

   Shown in the video
2. Expression

   $$v-e+f=2-1+1=2$$
   Explanation

   Substitute into Euler's expression.

   Justification

   This is the arithmetic shown on the slide.

   Shown in the video

For $P_2$, $v - e + f = 2$.

The slide directly states the result 2 after substitution.

1. Audio
   Observation

   Speaker walks through the numbers for $P_2$: 'number of vertices is two... edges is one... faces is one'.

2. Formula
   Observation

   Text displays '$v = 2$, $e = 1$ and $f = 1$, so $v - e + f = 2$'.

Find the value of $v - e + f$ for the path graph $P_2$.

1. Graph is $P_2$

2. $v = 2$

3. $e = 1$

4. $f = 1$

Compute $v - e + f$

1. Expression

   $$v - e + f$$
   Explanation

   Substitute the known values into the expression.

   Justification

   Definition of the invariant quantity.

   Shown in the video
2. Expression

   $$2 - 1 + 1$$
   Explanation

   Plug in $v=2$, $e=1$, $f=1$.

   Justification

   Given values for $P_2$.

   Shown in the video
3. Expression

   $$2$$
   Explanation

   Perform arithmetic.

   Justification

   Standard addition/subtraction.

   Derived from the video

2

Matches the general result stated for all planar graphs.

1. Audio
   Observation

   Speaker identifies $K_5$ as the smallest graph where edges must intersect.

2. Diagram
   Observation

   Image shows $K_5$ with crossing edges labeled 'Non-planar Graphs'.

Determine if the complete graph $K_5$ is planar.

1. Graph is $K_5$ (5 vertices, all connected)

2. Visual representation shows edge crossings

Check planarity

1. ExpressionEdges intersect in drawing
   Explanation

   Observe that in the standard drawing of $K_5$, edges cross each other.

   Justification

   Visual evidence from the slide.

   Shown in the video
2. ExpressionToo many edges for vertices
   Explanation

   The density of connections forces intersections in 2D plane.

   Justification

   Audio explanation: 'If there are too many edges and too few vertices...'

   Shown in the video

$K_5$ is non-planar.

Stated as the smallest example of a non-planar graph in the video.

1. Diagram
   Observation

   First slide titled “Planar graphs” shows text definitions and two graph drawings connected by a blue arrow.

2. Animation
   Observation

   A pop-up notice appears around 21–32 seconds stating both graphs have 5 vertices and the same vertex degrees.

3. Diagram
   Observation

   Around 57 seconds, red numerals 1, 2, and 3 appear on the right-hand graph to mark faces.

1. Title “Planar graphs”

2. Definition sentence

3. Left graph with crossings

4. Blue arrow

5. Right planar graph

6. Pop-up notice

7. Face labels 1, 2, 3

1. The slide remains mostly static while the cursor moves over text and diagrams.

2. A blue pop-up notice appears and later disappears.

3. Red face numbers are added to the right-hand graph.

1. The underlying lesson topic stays on planar graphs and faces.

2. The two graph drawings represent the same graph.

The visual sequence supports the distinction between a nonplanar-looking drawing and a planar representation, then identifies the faces of the planar drawing.

1. Diagram
   Observation

   Second slide titled “Planar graphs” shows a WARNING, two representations of the same graph, and Euler’s formula.

2. Diagram
   Observation

   Red numerals 1, 2, 3, and 4 appear on the right-hand graph to label faces.

1. Title “Planar graphs”

2. WARNING text

3. Left graph with crossing diagonals

4. Right planar graph

5. Face labels 1, 2, 3, 4

6. Euler’s formula line

1. The slide changes from the first example to the warning slide at about 78 seconds.

2. Face labels are added to the right-hand graph.

3. The formula $v - e + f = 2$ is displayed at the bottom.

1. Both drawings on this slide represent the same graph.

2. The lesson continues to emphasize planar representations for face counting.

The second slide visually contrasts an invalid face count from a crossing drawing with a valid count from a planar drawing, then introduces Euler’s formula.

1. Diagram
   Observation

   The first slide shows two drawings of the same graph side by side; the right drawing is planar and labels four faces 1, 2, 3, 4.

2. Caption evidence
   Observation

   The text warns that faces can only be counted when the graph is drawn in a planar way.

1. Left graph drawing with crossing edges

2. Right planar graph drawing

3. Four labeled face regions 1, 2, 3, 4

1. The presentation shifts attention from the left drawing to the right drawing.

2. The right drawing reveals the correct face decomposition of the same graph.

1. The underlying graph is the same in both drawings.

2. The warning text remains on screen throughout this interval.

The visual contrast demonstrates that face counting is representation-sensitive unless the drawing is planar.

1. Animation
   Observation

   At about 21 seconds the slide changes from the warning/formula slide to the proof-construction slide.

2. Caption evidence
   Observation

   The new slide begins with “Why is Euler's formula true?” and introduces $P_2$ and the two moves.

1. New slide title

2. Graph $P_2$

3. Two move diagrams

1. The previous warning example disappears.

2. The proof setup with $P_2$ and the two construction moves appears.

1. The topic remains Euler's formula for planar graphs.

The transition marks the shift from stating the theorem to justifying it by construction.

1. Diagram
   Observation

   The left diagram shows adding a new vertex connected by a new edge, labeled as a spike.

2. Diagram
   Observation

   The right diagram shows connecting two existing vertices with a new edge, described as completing a circuit.

1. Partial graph on the left

2. Dashed new edge and new vertex for the spike

3. Partial graph on the right

4. Dashed new edge between existing vertices

1. The left diagram illustrates growth by one vertex and one edge.

2. The right diagram illustrates growth by one edge only, closing a cycle.

1. Both diagrams are presented as allowed steps in building a connected planar graph.

The diagrams define the elementary operations used in the inductive proof.

1. Caption evidence
   Observation

   The slide now lists the effects of each move on v, e, and f and states the base-case calculation for $P_2$.

2. Diagram
   Observation

   A drawing of $K_5$ appears at the bottom right under the heading Non-planar Graphs.

1. Text describing spike effects

2. Text describing circuit effects

3. Base-case equation for $P_2$

4. Drawing of $K_5$

1. The proof slide expands from construction moves to their numerical effects.

2. The bottom section introduces non-planar graphs and $K_5$.

1. The central quantity under discussion remains $v - e + f$.

This visual layout connects the local move analysis to the global inductive conclusion and then contrasts planar graphs with a non-planar example.

1. Diagram
   Observation

   Top left diagrams show a square with a diagonal. Arrows indicate adding a vertex (spike) or connecting vertices (circuit).

1. Square graph with diagonal

2. Blue arrows

3. New vertex dot

4. Dashed line

1. A new vertex is added to an existing edge (spike).

2. Two existing vertices are connected by a new edge (circuit).

1. The overall structure remains a planar embedding during the demonstration.

These visuals demonstrate the two fundamental operations used to build complex planar graphs from simple ones while preserving the Euler characteristic.

1. Diagram
   Observation

   Bottom center image shows a pentagon with all diagonals drawn ($K_5$). Edges clearly cross inside the pentagon.

1. Pentagon vertices

2. Connecting lines (edges)

3. Intersection points

1. None (static image).

1. Edge crossings are visible.

This visual serves as a counter-example to planarity, showing a graph that cannot be drawn without intersections.

1. Audio
   Observation

   Narrator: “Even if a graph does not look like it is planar, it still might be.”

2. Diagram
   Observation

   A crossing drawing is redrawn without crossings.

If a graph is drawn with edge crossings, one may wrongly conclude that the graph itself is not planar.

Planarity depends on whether some drawing of the graph has no crossings, not on whether a particular drawing looks crossing-free.

1. Formula
   Observation

   Slide warning: “We can only count faces when the graph is drawn in a planar way.”

2. Audio
   Observation

   Narrator contrasts an apparent count of 5 faces with the correct count of 4 faces.

One may try to count faces directly from a drawing with edge crossings and obtain the wrong number.

Faces must be counted from a planar representation; otherwise the count is not the true face count of the planar graph.

1. Audio
   Observation

   Narrator: “yes we do include the outside region as a face.”

2. Formula
   Observation

   Slide text: “(yes, we do include the ‘outside’ region as a face).”

One may count only the bounded interior regions and omit the unbounded outside region.

The outside region is included as a face when counting faces of a planar graph.

1. Caption evidence
   Observation

   The slide warns that if one tries to count faces using the graph on the left, one might say there are 5 faces including the outside, but the planar representation shows only 4 faces.

One may incorrectly count 5 faces by looking at a drawing with edge crossings.

Faces should be counted only after redrawing the graph in a planar way; the planar representation shows 4 faces.

1. Caption evidence
   Observation

   The formula is stated specifically for any connected planar graph.

2. Caption evidence
   Observation

   A later section explicitly says not all graphs are planar and gives $K_5$ as an example.

One might think $v - e + f = 2$ holds for arbitrary graphs.

In this segment the formula is asserted only for connected planar graphs; non-planar graphs such as $K_5$ are treated separately.

1. Audio
   Observation

   Speaker explicitly states 'Not all graphs are planar.'

2. Formula
   Observation

   Section header 'Non-planar Graphs'.

Students might assume any graph can be drawn on a plane without edges crossing.

Graphs with high edge density relative to vertices, like $K_5$, force edge intersections and are therefore non-planar.

1. Audio
   Observation

   Narrator defines planar graphs and then immediately defines faces arising from such a drawing.

2. Formula
   Observation

   Slide text links planar drawing to division of the plane into faces.

The notion of faces is introduced only after specifying a planar drawing of a connected graph.

1. Audio
   Observation

   Narrator says the graph can be redrawn without crossings and then counts faces in the planar drawing.

2. Diagram
   Observation

   The right-hand planar drawing is used for face labeling.

A planar representation is needed before the face count can be meaningfully discussed as a property of the graph.

1. Formula
   Observation

   Euler’s formula is stated using v, e, and f after the lesson has defined faces.

Euler’s formula uses the number of faces, so the concept of a face must be understood first.

1. Formula
   Observation

   The slide explicitly restricts Euler’s formula to any connected planar graph.

Euler’s formula is presented specifically for connected planar graphs.

1. Formula
   Observation

   The WARNING text directly governs how faces should be counted.

The warning operationalizes the rule that face counting is valid only for planar drawings.

1. Caption evidence
   Observation

   The warning about planar face counting precedes the statement of Euler's formula on the same slide.

Correct face counting in a planar representation is needed before the quantities in Euler's formula are meaningful.

1. Caption evidence
   Observation

   After stating the formula, the next slide asks “Why is Euler's formula true?” and introduces the construction method.

The construction method is introduced specifically to justify Euler's formula.

1. Caption evidence
   Observation

   The method slide defines the spike as one of the two allowed moves.

The inductive construction method includes the spike move as one of its basic operations.

1. Caption evidence
   Observation

   The method slide defines connecting two existing vertices as the other allowed move.

The inductive construction method includes the circuit-completing move as its second basic operation.

1. Caption evidence
   Observation

   The slide contrasts planar graphs with the statement “Not all graphs are planar” and shows $K_5$.

Euler's formula is presented for connected planar graphs, while the final section contrasts them with non-planar graphs such as $K_5$.

1. Audio
   Observation

   Speaker links the construction method to the proof type: 'This argument is essentially a proof by induction.'

The derivation using spike and circuit operations provides the inductive step necessary to prove Euler's formula for all connected planar graphs.

1. Audio
   Observation

   Contrast between planar discussion and 'Not all graphs are planar... smallest... is $K_5$'.

Euler's formula applies to planar graphs; $K_5$ is introduced specifically as a non-planar graph where such planar embeddings fail.

1. Audio
   Observation

   Opening definition of planar graph.

2. Formula
   Observation

   Definition box on slide 1.

1. Definition of a planar graph

1. Audio
   Observation

   Narrator defines faces and includes the outside region.

2. Diagram
   Observation

   Face labels 1, 2, 3 on the planar drawing.

1. Faces of a planar embedding
2. Forgetting the outside region

1. Diagram
   Observation

   Left crossing graph transformed into right planar graph.

2. Audio
   Observation

   Narrator explains that a graph may still be planar if it can be redrawn without crossings.

1. Planar representation versus nonplanar drawing
2. Mistaking a bad drawing for a nonplanar graph

1. Diagram
   Observation

   Right-hand graph labeled with 1, 2, 3.

2. Audio
   Observation

   Narrator counts two inner regions and one outside region.

1. Example: a graph that looks nonplanar but is planar
2. Counting faces in the first example graph

1. Formula
   Observation

   WARNING text on slide 2.

2. Audio
   Observation

   Narrator says faces can only be counted in a planar way.

1. Faces may be counted only from a planar drawing
2. Counting faces from a nonplanar drawing

1. Diagram
   Observation

   Two drawings of the same graph, with the planar one labeled 1–4.

2. Audio
   Observation

   Narrator contrasts 5 apparent faces with 4 actual faces.

1. Example: why face counting fails on a crossing drawing
2. Why the second example has 4 faces, not 5

1. Formula
   Observation

   Slide displays $v - e + f = 2$ for connected planar graphs.

1. The spoken explanation is incomplete in this clip.

1. Euler’s formula for connected planar graphs
2. Euler’s formula statement

1. Caption evidence
   Observation

   The slide states the formula explicitly.

1. Euler's formula for connected planar graphs

1. Caption evidence
   Observation

   The slide warns that faces can only be counted when the graph is drawn in a planar way.

1. Faces must be counted from a planar drawing
2. Counting faces from a non-planar drawing

1. Caption evidence
   Observation

   The slide asks why Euler's formula is true and lays out the construction from $P_2$.

1. Proof method: build any connected planar graph from $P_2$ by two moves
2. Inductive justification of Euler's formula

1. Caption evidence
   Observation

   The slide labels the left move as adding a new vertex connected by a new edge, called a spike.

1. Spike move
2. A spike preserves $v - e + f$

1. Caption evidence
   Observation

   The slide states that completing a circuit adds one edge and one face while keeping vertices the same.

1. Circuit-completing move
2. Completing a circuit preserves $v - e + f$