Ch.4: Planar Graphs

From the lecture notes "Combinatorics, Graphs, Matroids" (University of Bonn, winter term 2025/26) 4.1. Basic Definitions and Results 4.2. Kuratowski-Wagner Theorem

73 flashcards · Mathematics · by lakesare

Part of University of Bonn › V3C2: Combinatorics, Graphs, Matroids · 6 courses

1. [Basic Definitions and Results] In the course's treatment of planar graphs, may a graph have loops and parallel edges?

   Yes, both (unless stated otherwise). Graphs are undirected. e={v,w}e = \{v, w\}e={v,w} still denotes an edge eee connecting vvv and www , even when there are several such edges.

2. [Basic Definitions and Results] What is a simple Jordan curve?

   The image of a continuous injective function ϕ:[0,1]→R2\phi : [0, 1] \to \mathbb{R}^2ϕ:[0,1]→R2 . Its endpoints are ϕ(0)\phi(0)ϕ(0) and ϕ(1)\phi(1)ϕ(1) .

3. [Basic Definitions and Results] What is a closed Jordan curve?

   The image of a continuous ϕ:[0,1]→R2\phi : [0, 1] \to \mathbb{R}^2ϕ:[0,1]→R2 with ϕ(0)=ϕ(1)\phi(0) = \phi(1)ϕ(0)=ϕ(1) and ϕ(τ)≠ϕ(τ′)\phi(\tau) \ne \phi(\tau&#x27;)ϕ(τ)=ϕ(τ′) for 0≤τ<τ′<10 \le \tau < \tau&#x27; < 10≤τ<τ′<1 . Injective except that the start and end meet.

4. [Basic Definitions and Results] What are a polygonal arc and a polygon?

   Polygonal arc: a simple Jordan curve that is a union of finitely many straight line segments. Polygon: a closed Jordan curve that is a union of finitely many straight line segments.

5. [Basic Definitions and Results] J⊆R2J \subseteq \mathbb{R}^2J⊆R2 is a union of finitely many line segments and R=R2∖JR = \mathbb{R}^2 \setminus JR=R2∖J . What are the connected regions of RRR ?

   The equivalence classes of points of RRR , where two points are equivalent if a polygonal arc within RRR joins them.

6. [Basic Definitions and Results] What is a planar embedding of a graph GGG ?

   Distinct points ψ(v)\psi(v)ψ(v) for the vertices and for each edge eee a polygonal arc JeJ_eJe​ joining the points of its two ends (a polygon through ψ(x)\psi(x)ψ(x) for a loop at xxx ), such that no JeJ_eJe​ meets a vertex point or another edge's curve except at its own endpoints. For each e={x,y}∈E(G)e = \{x, y\} \in E(G)e={x,y}∈E(G) : (Je∖{ψ(x),ψ(y)})∩({ψ(v)∣v∈V(G)}∪⋃e′∈E(G)∖{e}Je′)=∅\displaystyle (J_e \setminus \{\psi(x), \psi(y)\}) \cap \Bigl(\{\psi(v) \mid v \in V(G)\} \cup \bigcup_{e&#x2…

7. [Basic Definitions and Results] A graph is called planar if it has a planar embedding.

8. [Basic Definitions and Results] Φ=(ψ,(Je)e∈E(G))\Phi = (\psi, (J_e)_{e \in E(G)})Φ=(ψ,(Je​)e∈E(G)​) is a planar embedding of GGG : ψ\psiψ places the vertices, JeJ_eJe​ is the polygonal arc (or, for a loop, the polygon) drawing the edge eee .What are the faces of Φ\PhiΦ ?

   The open connected regions into which R2∖({ψ(v)∣v∈V(G)}∪⋃e∈E(G)Je)\mathbb{R}^2 \setminus \bigl(\{\psi(v) \mid v \in V(G)\} \cup \bigcup_{e \in E(G)} J_e\bigr)R2∖({ψ(v)∣v∈V(G)}∪⋃e∈E(G)​Je​) splits. The plane with the drawing of GGG removed falls apart into faces.

9. [Basic Definitions and Results] Exactly one face of a planar embedding is unbounded; it is called the outer face.

10. [Basic Definitions and Results] Jordan curve theorem. What does R2∖J\mathbb{R}^2 \setminus JR2∖J look like if JJJ is a polygon, and if JJJ is a polygonal arc?

    Polygon: exactly two connected regions, each having JJJ as its boundary. Polygonal arc: one connected region. It seems obvious but needs a proof (the notes refer to Korte and Vygen).

11. [Basic Definitions and Results] GGG is a simple connected planar graph with a planar embedding. When is R2\mathbb{R}^2R2 minus the drawing of GGG (all vertex points and edge curves) connected?

    If and only if GGG is a tree. So among simple connected graphs, exactly the trees have embeddings with a single face.

12. [Basic Definitions and Results] GGG is a simple connected planar graph, and RRR is R2\mathbb{R}^2R2 minus the drawing of GGG in some planar embedding.Why is RRR disconnected if GGG is not a tree?

    GGG contains a cycle, whose drawing is a polygon splitting R2\mathbb{R}^2R2 into two regions, and both regions meet RRR . By the Jordan curve theorem.

13. [Basic Definitions and Results] GGG is a tree with a planar embedding, and RRR is R2\mathbb{R}^2R2 minus the drawing of GGG .How does the proof that RRR is connected go?

    Induction on ∣V(G)∣+∣E(G)∣|V(G)| + |E(G)|∣V(G)∣+∣E(G)∣ : remove the edge e~={v,w}\tilde e = \{v, w\}e~={v,w} at a leaf vvv ; a polygonal arc between p,q∈Rp, q \in Rp,q∈R that hits Je~J_{\tilde e}Je~​ is rerouted along Je~J_{\tilde e}Je~​ around its free end ψ(v)\psi(v)ψ(v) . Without Je~J_{\tilde e}Je~​ the region is connected by induction. If the arc from ppp to qqq meets Je~J_{\tilde e}Je~​ , then ppp and qqq both reach points arbitrarily close to Je~J_{\tilde e}Je~​ , and following Je~J_{\til…

14. [Basic Definitions and Results] Φ=(ψ,(Je)e∈E(G))\Phi = (\psi, (J_e)_{e \in E(G)})Φ=(ψ,(Je​)e∈E(G)​) is a planar embedding of GGG : ψ\psiψ places the vertices, JeJ_eJe​ is the polygonal arc (or, for a loop, the polygon) drawing the edge eee .What is the planar dual G∗G^*G∗ of GGG (with respect to Φ\PhiΦ )?

    Vertices: the faces of Φ\PhiΦ . Edges: one edge e∗e^*e∗ for each e∈E(G)e \in E(G)e∈E(G) , connecting the faces adjacent to JeJ_eJe​ . If eee is adjacent to only one face, e∗e^*e∗ is a loop.

15. [Basic Definitions and Results] GGG is a tree with nnn vertices, embedded in the plane. What is its planar dual G∗G^*G∗ ?

    One vertex with n−1n - 1n−1 loops. A tree's embedding has a single face (Euler: (n−1)−n+2=1(n - 1) - n + 2 = 1(n−1)−n+2=1 ), and every edge has that face on both sides.

16. [Basic Definitions and Results] The cycle CnC_nCn​ ( n≥3n \ge 3n≥3 ) is embedded in the plane. What is its planar dual?

    Two vertices joined by nnn parallel edges. By the Jordan curve theorem there are two faces, inside and outside, and every edge lies between them.

17. [Basic Definitions and Results] GGG is a planar graph with planar embedding Φ\PhiΦ , and G∗G^*G∗ is its planar dual: faces of Φ\PhiΦ as vertices, one edge e∗e^*e∗ per edge eee of GGG , joining the faces on the two sides of JeJ_eJe​ .What is a standard embedding of G∗G^*G∗ ?

    A planar embedding of G∗G^*G∗ with each dual vertex ψ∗(F)\psi^*(F)ψ∗(F) inside its face FFF , and each dual edge Je∗J_{e^*}Je∗​ crossing JeJ_eJe​ exactly once and meeting no other part of the drawing of GGG . Formally ∣Je∗∩Je∣=1|J_{e^*} \cap J_e| = 1∣Je∗​∩Je​∣=1 and Je∗J_{e^*}Je∗​ avoids all ψ(v)\psi(v)ψ(v) and all JfJ_fJf​ , f≠ef \ne ef=e . If e∗e^*e∗ is a loop, the face bounded by Je∗J_{e^*}Je∗​ contains exactly one endpoint of eee . Such an embedding always exists, so G∗G^*G∗ is planar.

18. [Basic Definitions and Results] Does the planar dual G∗G^*G∗ depend only on the graph GGG ?

    No, it depends on the chosen planar embedding of GGG . Its number of vertices does not, for connected GGG : it is the number of faces, ∣E(G)∣−∣V(G)∣+2|E(G)| - |V(G)| + 2∣E(G)∣−∣V(G)∣+2 by Euler's formula.

19. [Basic Definitions and Results] GGG is a simple connected planar graph with a planar embedding, G∗G^*G∗ is its planar dual with standard embedding, and TTT is a spanning tree of GGG .Which edges of G∗G^*G∗ form a spanning tree of G∗G^*G∗ ?

    The duals e∗e^*e∗ of the edges eee not in TTT : (V(G∗),F∗)(V(G^*), F^*)(V(G∗),F∗) with F∗={e∗∣e∈E(G)∖E(T)}F^* = \{e^* \mid e \in E(G) \setminus E(T)\}F∗={e∗∣e∈E(G)∖E(T)} is a spanning tree.

20. [Basic Definitions and Results] GGG is simple, connected, planar and embedded, G∗G^*G∗ is its planar dual (standard embedding), and TTT is a spanning tree of GGG . Then the duals F∗={e∗∣e∈E(G)∖E(T)}F^* = \{e^* \mid e \in E(G) \setminus E(T)\}F∗={e∗∣e∈E(G)∖E(T)} of the edges outside TTT form a spanning tree (V(G∗),F∗)(V(G^*), F^*)(V(G∗),F∗) of G∗G^*G∗ .Why is (V(G∗),F∗)(V(G^*), F^*)(V(G∗),F∗) connected?

    TTT is a tree, so R2\mathbb{R}^2R2 minus the drawing of TTT is connected: any two faces are joined by a curve crossing only edges outside TTT , i.e. moving along dual edges in F∗F^*F∗ . R2\mathbb{R}^2R2 minus the drawing of a simple connected graph is connected exactly for trees.

21. [Basic Definitions and Results] GGG is simple, connected, planar and embedded, G∗G^*G∗ is its planar dual (standard embedding), and TTT is a spanning tree of GGG . Then the duals F∗={e∗∣e∈E(G)∖E(T)}F^* = \{e^* \mid e \in E(G) \setminus E(T)\}F∗={e∗∣e∈E(G)∖E(T)} of the edges outside TTT form a spanning tree (V(G∗),F∗)(V(G^*), F^*)(V(G∗),F∗) of G∗G^*G∗ .Why does (V(G∗),F∗)(V(G^*), F^*)(V(G∗),F∗) contain no cycle?

    A cycle CCC in F∗F^*F∗ is drawn as a polygon separating the two ends v,wv, wv,w of an edge eee whose dual e∗e^*e∗ lies on CCC ; but the vvv – www path in TTT would join them without crossing CCC . Je∗J_{e^*}Je∗​ crosses JeJ_eJe​ exactly once, so ψ(v)\psi(v)ψ(v) and ψ(w)\psi(w)ψ(w) lie in different regions. The path in TTT avoids the drawing of CCC , since dual edges in F∗F^*F∗ cross only edges outside TTT . Contradiction to TTT being connected.

22. [Basic Definitions and Results] Euler's formula. GGG is a connected planar graph. How many faces does a planar embedding of GGG have?

    ∣E(G)∣−∣V(G)∣+2\boldsymbol{|E(G)| - |V(G)| + 2}∣E(G)∣−∣V(G)∣+2 , for every embedding.

23. [Basic Definitions and Results] GGG is simple, connected, planar and embedded, G∗G^*G∗ is its planar dual (standard embedding), and TTT is a spanning tree of GGG . Then the duals F∗={e∗∣e∈E(G)∖E(T)}F^* = \{e^* \mid e \in E(G) \setminus E(T)\}F∗={e∗∣e∈E(G)∖E(T)} of the edges outside TTT form a spanning tree (V(G∗),F∗)(V(G^*), F^*)(V(G∗),F∗) of G∗G^*G∗ .How does this prove Euler's formula (number of faces =∣E(G)∣−∣V(G)∣+2= |E(G)| - |V(G)| + 2=∣E(G)∣−∣V(G)∣+2 )?

    Count edges of the two spanning trees: ∣E(T)∣=∣V(G)∣−1|E(T)| = |V(G)| - 1∣E(T)∣=∣V(G)∣−1 , ∣F∗∣=∣V(G∗)∣−1|F^*| = |V(G^*)| - 1∣F∗∣=∣V(G∗)∣−1 , and together they are all edges: ∣E(T)∣+∣F∗∣=∣E(G)∣|E(T)| + |F^*| = |E(G)|∣E(T)∣+∣F∗∣=∣E(G)∣ . So ∣E(G)∣=∣V(G)∣+∣V(G∗)∣−2|E(G)| = |V(G)| + |V(G^*)| - 2∣E(G)∣=∣V(G)∣+∣V(G∗)∣−2 , and ∣V(G∗)∣|V(G^*)|∣V(G∗)∣ is the number of faces.

24. [Basic Definitions and Results] A connected planar graph has 8 vertices and 12 edges (e.g. the cube Q3Q_3Q3​ ). How many faces does each of its planar embeddings have?

    6 Euler's formula: 12−8+2=612 - 8 + 2 = 612−8+2=6 .

25. [Basic Definitions and Results] Let k≥2k \ge 2k≥2 . When is a graph kkk -connected?

    It has more than kkk nodes and stays connected after removing any k−1k - 1k−1 nodes.

26. [Basic Definitions and Results] Let k≥2k \ge 2k≥2 . When is a graph kkk -edge-connected?

    It has at least two nodes and stays connected after removing any k−1k - 1k−1 edges.

27. [Basic Definitions and Results] Is the complete graph K4K_4K4​ 3-connected? Is it 4-connected?

    3-connected: yes. 4-connected: no. kkk -connected requires more than kkk nodes, and K4K_4K4​ has only 4.

28. [Basic Definitions and Results] Two triangles share one vertex (and nothing else). Is the graph 2-connected? Is it 2-edge-connected?

    Not 2-connected, but 2-edge-connected. Removing the shared vertex disconnects it; removing a single edge never does, since every edge lies on a triangle.

29. [Basic Definitions and Results] For graphs GGG and HHH , what is G+HG + HG+H ?

    The graph with node set V(G)∪V(H)V(G) \cup V(H)V(G)∪V(H) and edge set E(G)∪˙E(H)E(G) \mathbin{\dot\cup} E(H)E(G)∪˙E(H) (disjoint union of the edges).

30. [Basic Definitions and Results] What is an ear-decomposition of a graph GGG ?

    A sequence r,P1,…,Pkr, P_1, \dots, P_kr,P1​,…,Pk​ with G=({r},∅)+P1+⋯+PkG = (\{r\}, \emptyset) + P_1 + \dots + P_kG=({r},∅)+P1​+⋯+Pk​ , where each ear PiP_iPi​ is a path whose endpoints (and only those) lie in {r}∪V(P1)∪⋯∪V(Pi−1)\{r\} \cup V(P_1) \cup \dots \cup V(P_{i-1}){r}∪V(P1​)∪⋯∪V(Pi−1​) , or a circuit with exactly one vertex there. Start from a single vertex rrr and keep attaching ears to what is already built.

31. [Basic Definitions and Results] When is an ear-decomposition r,P1,…,Pkr, P_1, \dots, P_kr,P1​,…,Pk​ proper?

    k≥1k \ge 1k≥1 , P1P_1P1​ is a circuit of length at least three, and P2,…,PkP_2, \dots, P_kP2​,…,Pk​ are paths.

32. [Basic Definitions and Results] Whitney's theorem. Which graphs without loops have a proper ear-decomposition (a circuit of length ≥3\ge 3≥3 , then only path ears)?

    Exactly the 2-connected ones.

33. [Basic Definitions and Results] Whitney: a graph without loops is 2-connected if and only if it has a proper ear-decomposition (a circuit of length ≥3\ge 3≥3 , then paths whose two endpoints, and only those, lie in the graph built so far).Why is a graph with a proper ear-decomposition 2-connected?

    A circuit of length ≥3\ge 3≥3 is 2-connected, and adding an xxx – yyy path ( x≠yx \ne yx=y ) to a 2-connected graph keeps it 2-connected. Induction on the number of ears.

34. [Basic Definitions and Results] Whitney: a graph without loops is 2-connected if and only if it has a proper ear-decomposition (a circuit of length ≥3\ge 3≥3 , then paths whose two endpoints, and only those, lie in the graph built so far).For a 2-connected loopless GGG , why does GGG contain at least one subgraph with a proper ear-decomposition?

    A maximal simple subgraph G′G&#x27;G′ of GGG is still 2-connected, so it is not a tree and contains a circuit of length ≥3\ge 3≥3 , which is a proper ear-decomposition by itself. Simple means circuits have length at least 3: parallel edges and loops are dropped.

35. [Basic Definitions and Results] Whitney: a graph without loops is 2-connected if and only if it has a proper ear-decomposition (a circuit of length ≥3\ge 3≥3 , then paths whose two endpoints, and only those, lie in the graph built so far). GGG is 2-connected and HHH is a maximal subgraph of GGG with a proper ear-decomposition.Why does HHH contain all vertices of GGG ?

    Otherwise there is an edge e={x,y}e = \{x, y\}e={x,y} with x∈V(H)x \in V(H)x∈V(H) , y∉V(H)y \notin V(H)y∈/V(H) ; a path in G−xG - xG−x from yyy to HHH , together with eee , is a new ear. That contradicts maximality. Pick z∈V(H)∖{x}z \in V(H) \setminus \{x\}z∈V(H)∖{x} ; G−xG - xG−x is connected, so it has a yyy – zzz path PPP . Stop PPP at its first vertex z′z&#x27;z′ in V(H)V(H)V(H) : then P[y,z′]+eP_{[y, z&#x27;]} + eP[y,z′]​+e is a path with exactly its endpoints x≠z′x \ne z&#x27;x=z′ in HHH…

36. [Basic Definitions and Results] Whitney: a graph without loops is 2-connected if and only if it has a proper ear-decomposition (a circuit of length ≥3\ge 3≥3 , then paths whose two endpoints, and only those, lie in the graph built so far). GGG is 2-connected and loopless, and HHH is a spanning subgraph of GGG with a proper ear-decomposition.Why can HHH be extended to all of GGG ?

    Every remaining edge of E(G)∖E(H)E(G) \setminus E(H)E(G)∖E(H) is a path of length 1 between two distinct vertices of HHH , so it can be added as an ear. Distinct, because GGG has no loops.

37. [Basic Definitions and Results] A triangle with an extra loop at one vertex is 2-connected. Why has it no proper ear-decomposition?

    The loop could only be added as a circuit ear, but in a proper ear-decomposition only P1P_1P1​ is a circuit, and P1P_1P1​ has length ≥3\ge 3≥3 . This is why Whitney's theorem is stated for graphs without loops.

38. [Basic Definitions and Results] GGG is a 2-edge-connected planar graph with a planar embedding. On the boundary of how many faces is each edge?

    Exactly two. No edge can be on the boundary of more than two faces.

39. [Basic Definitions and Results] GGG is a 2-edge-connected planar graph with a planar embedding.Why can an edge eee of GGG not lie on the boundary of just one face?

    Then e∗e^*e∗ would be a loop, so in no spanning tree of G∗G^*G∗ , so eee lies in every spanning tree of GGG , i.e. eee is a bridge. That contradicts 2-edge-connectivity. For a spanning tree TTT of GGG , the duals of the edges outside TTT form a spanning tree of the dual G∗G^*G∗ ; so e∉E(T)e \notin E(T)e∈/E(T) would put the loop e∗e^*e∗ into a spanning tree.

40. [Basic Definitions and Results] GGG is a 2-connected planar graph without loops, with a planar embedding Φ\PhiΦ . What bounds each face of Φ\PhiΦ ?

    A polygon that is the drawing of a circuit of GGG .

41. [Basic Definitions and Results] GGG is a 2-connected planar graph without loops, with a planar embedding Φ\PhiΦ . Claim: every face of Φ\PhiΦ is bounded by the drawing of a circuit.How is this proved?

    Induction on ∣E(G)∣|E(G)|∣E(G)∣ along a proper ear-decomposition: the last ear PPP (an xxx – yyy path) runs through one face FFF of the smaller graph and splits it into two faces, each bounded by a circuit. Base case: GGG is a circuit, and the Jordan curve theorem applies.

42. [Basic Definitions and Results] GGG is 2-connected and loopless with a planar embedding; PPP is the last ear (an xxx – yyy path) of a proper ear-decomposition, G′G&#x27;G′ is GGG without PPP , and the drawing of PPP lies in a face FFF of G′G&#x27;G′ , which is bounded by (the drawing of) a circuit CCC .Why does FFF split into two faces bounded by circuits?

    CCC contains xxx and yyy , so it is the union of two xxx – yyy paths Q1,Q2Q_1, Q_2Q1​,Q2​ ; by the Jordan curve theorem, PPP splits FFF into two faces bounded by the circuits Q1+PQ_1 + PQ1​+P and Q2+PQ_2 + PQ2​+P . All other faces of G′G&#x27;G′ remain faces of GGG .

43. [Basic Definitions and Results] What is the girth g(G)g(G)g(G) of a graph GGG ?

    The length of a shortest circuit in GGG (loops count, with length 1); g(G)=∞g(G) = \inftyg(G)=∞ if GGG has no circuit.

44. [Basic Definitions and Results] What is the girth of: a tree, KnK_nKn​ ( n≥3n \ge 3n≥3 ), K3,3K_{3,3}K3,3​ , and a loopless graph with two parallel edges?

    ∞\infty∞ , 3, 4, 2. K3,3K_{3,3}K3,3​ is bipartite, so it has no odd circuit; two parallel edges form a circuit of length 2.

45. [Basic Definitions and Results] GGG is a 2-connected simple planar graph with nnn vertices and girth kkk . At most how many edges does GGG have?

    (n−2)kk−2\boldsymbol{(n - 2) \dfrac{k}{k - 2}}(n−2)k−2k​

46. [Basic Definitions and Results] A simple planar graph has n≥3n \ge 3n≥3 vertices. At most how many edges does it have?

    3n−6\boldsymbol{3n - 6}3n−6

47. [Basic Definitions and Results] GGG is a 2-connected simple planar graph with nnn vertices, mmm edges and girth kkk . Claim: m≤(n−2)kk−2m \le (n - 2) \frac{k}{k - 2}m≤(n−2)k−2k​ .What is the proof?

    Count face boundaries: r=m−n+2r = m - n + 2r=m−n+2 faces (Euler), each bounded by a circuit of ≥k\ge k≥k edges, each edge on exactly two faces, so kr≤2mkr \le 2mkr≤2m . Then m−n+2≤2kmm - n + 2 \le \frac{2}{k} mm−n+2≤k2​m , i.e. m≤(n−2)kk−2m \le (n - 2) \frac{k}{k - 2}m≤(n−2)k−2k​ . Faces are bounded by circuits since GGG is 2-connected and loopless; each edge is on two faces since GGG is 2-edge-connected.

48. [Basic Definitions and Results] A 2-connected simple planar graph with nnn vertices and girth kkk has at most (n−2)kk−2(n - 2) \frac{k}{k - 2}(n−2)k−2k​ edges.How does this give 3n−63n - 63n−6 for every simple planar graph with n≥3n \ge 3n≥3 vertices?

    Add edges until the graph is 2-connected, keeping it simple and planar; then the girth kkk is ≥3\ge 3≥3 , and (n−2)kk−2≤(n−2)33−2=3n−6(n - 2) \frac{k}{k - 2} \le (n - 2) \frac{3}{3 - 2} = 3n - 6(n−2)k−2k​≤(n−2)3−23​=3n−6 . kk−2\frac{k}{k - 2}k−2k​ decreases in kkk . Adding edges only increases the edge count, so the bound holds for the original graph too.

49. [Basic Definitions and Results] GGG is a 2-connected simple bipartite planar graph with nnn vertices. At most how many edges does it have?

    2n−4\boldsymbol{2n - 4}2n−4 Bipartite means no odd circuits, so girth k≥4k \ge 4k≥4 and (n−2)kk−2≤(n−2)42(n - 2) \frac{k}{k - 2} \le (n - 2) \frac{4}{2}(n−2)k−2k​≤(n−2)24​ .

50. [Basic Definitions and Results] Why are neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ planar?

    K5K_5K5​ : 10>3⋅5−6=910 > 3 \cdot 5 - 6 = 910>3⋅5−6=9 edges. K3,3K_{3,3}K3,3​ : 2-connected with girth 4, and 9>(6−2)44−2=89 > (6 - 2) \frac{4}{4 - 2} = 89>(6−2)4−24​=8 edges. A simple planar graph with n≥3n \ge 3n≥3 vertices has at most 3n−63n - 63n−6 edges; a 2-connected one with girth kkk at most (n−2)kk−2(n - 2) \frac{k}{k - 2}(n−2)k−2k​ .

51. [Basic Definitions and Results] Why does the bound "a simple planar graph with n≥3n \ge 3n≥3 vertices has at most 3n−63n - 63n−6 edges" not show that K3,3K_{3,3}K3,3​ is nonplanar?

    K3,3K_{3,3}K3,3​ has 9 edges and 3⋅6−6=12≥93 \cdot 6 - 6 = 12 \ge 93⋅6−6=12≥9 . The girth bound (n−2)kk−2(n - 2) \frac{k}{k - 2}(n−2)k−2k​ with k=4k = 4k=4 gives 8 instead.

52. [Basic Definitions and Results] The Petersen graph is 3-connected with 10 vertices, 15 edges and girth 5. Why is it not planar?

    A 2-connected simple planar graph with girth 5 on 10 vertices has at most (10−2)53=403<15(10 - 2) \frac{5}{3} = \frac{40}{3} < 15(10−2)35​=340​<15 edges. The bound 3n−6=243n - 6 = 243n−6=24 is too weak here.

53. [Kuratowski-Wagner Theorem] When are two graphs GGG and HHH (parallel edges allowed) isomorphic?

    There are bijections ΦV:V(G)→V(H)\Phi_V : V(G) \to V(H)ΦV​:V(G)→V(H) and ΦE:E(G)→E(H)\Phi_E : E(G) \to E(H)ΦE​:E(G)→E(H) with ΦE({v,w})={ΦV(v),ΦV(w)}\Phi_E(\{v, w\}) = \{\Phi_V(v), \Phi_V(w)\}ΦE​({v,w})={ΦV​(v),ΦV​(w)} for every edge {v,w}\{v, w\}{v,w} . The edge bijection is needed because of parallel edges.

54. [Kuratowski-Wagner Theorem] GGG is a graph and X⊆V(G)X \subseteq V(G)X⊆V(G) . What is G/XG/XG/X , the graph obtained by contracting XXX ?

    Delete the vertices of XXX and the edges of G[X]G[X]G[X] , add a new vertex xxx , and replace each edge {v,w}\{v, w\}{v,w} with v∈Xv \in Xv∈X , w∉Xw \notin Xw∈/X by an edge {x,w}\{x, w\}{x,w} . Parallel edges may arise.

55. [Kuratowski-Wagner Theorem] What do you get by contracting one edge of the triangle K3K_3K3​ ?

    Two vertices joined by two parallel edges. Contracting X={a,b}X = \{a, b\}X={a,b} deletes the edge ababab ; the edges acacac and bcbcbc both become xcxcxc .

56. [Kuratowski-Wagner Theorem] When is a graph GGG a minor of a graph HHH ?

    Some subgraph H′H&#x27;H′ of HHH has a partition V(H′)=V1∪˙⋯∪˙VkV(H&#x27;) = V_1 \mathbin{\dot\cup} \dots \mathbin{\dot\cup} V_kV(H′)=V1​∪˙⋯∪˙Vk​ into connected subsets such that contracting each ViV_iVi​ gives a graph isomorphic to GGG .

57. [Kuratowski-Wagner Theorem] GGG and HHH are graphs, and GGG has no loops. Which operations on HHH produce GGG exactly when GGG is a minor of HHH ?

    A series of vertex deletions, edge deletions and edge contractions.

58. [Kuratowski-Wagner Theorem] HHH is planar and GGG is a minor of HHH . Is GGG planar? What follows for K5K_5K5​ and K3,3K_{3,3}K3,3​ ?

    Yes, GGG is planar. So a graph with K5K_5K5​ or K3,3K_{3,3}K3,3​ as a minor is not planar.

59. [Kuratowski-Wagner Theorem] Lemma (Tutte, Thomassen). GGG is a 3-connected graph with at least five vertices. What edge exists in GGG ?

    An edge eee such that G/eG/eG/e ( eee contracted to a single vertex) is also 3-connected.

60. [Kuratowski-Wagner Theorem] Lemma (Tutte, Thomassen): every 3-connected graph GGG with at least 5 vertices has an edge eee such that G/eG/eG/e ( GGG with eee contracted to a single vertex) is 3-connected.Why is "at least 5 vertices" needed?

    For K4K_4K4​ (3-connected), contracting any edge leaves only 3 vertices, and a 3-connected graph needs more than 3.

61. [Kuratowski-Wagner Theorem] GGG is 3-connected, e={v,w}e = \{v, w\}e={v,w} is an edge, and G/eG/eG/e is not 3-connected.What does this give in GGG ?

    A vertex xxx such that G−{x,v,w}G - \{x, v, w\}G−{x,v,w} is disconnected. G/eG/eG/e has two vertices whose removal disconnects it. One of them is the vertex made from eee , otherwise those two vertices would also disconnect GGG .

62. [Kuratowski-Wagner Theorem] Proof that a 3-connected GGG with ≥5\ge 5≥5 vertices has an edge eee with G/eG/eG/e 3-connected. Assume no such edge exists. Then every edge {v,w}\{v, w\}{v,w} has a vertex xxx with G−{x,v,w}G - \{x, v, w\}G−{x,v,w} disconnected. Choose the edge {v,w}\{v, w\}{v,w} , the vertex xxx and a component CCC of G−{x,v,w}G - \{x, v, w\}G−{x,v,w} with ∣V(C)∣|V(C)|∣V(C)∣ minimal.Why does xxx have a neighbor yyy in CCC ?

    Otherwise CCC is a connected component of G−{v,w}G - \{v, w\}G−{v,w} , so removing two vertices disconnects GGG , contradicting 3-connectivity.

63. [Kuratowski-Wagner Theorem] Proof that a 3-connected GGG with ≥5\ge 5≥5 vertices has an edge eee with G/eG/eG/e 3-connected. Assume no such edge exists. Then every edge {v,w}\{v, w\}{v,w} has a vertex xxx with G−{x,v,w}G - \{x, v, w\}G−{x,v,w} disconnected. Choose the edge {v,w}\{v, w\}{v,w} , the vertex xxx and a component CCC of G−{x,v,w}G - \{x, v, w\}G−{x,v,w} with ∣V(C)∣|V(C)|∣V(C)∣ minimal. Then xxx has a neighbor yyy in CCC , and (as G/{x,y}G/\{x, y\}G/{x,y} is not 3-connected) there is…

    vvv and www are adjacent, so those of them that are not removed lie in a single component; since there are at least two components, another one avoids both.

64. [Kuratowski-Wagner Theorem] Proof that a 3-connected GGG with ≥5\ge 5≥5 vertices has an edge eee with G/eG/eG/e 3-connected. Assume no such edge exists. Then every edge {v,w}\{v, w\}{v,w} has a vertex xxx with G−{x,v,w}G - \{x, v, w\}G−{x,v,w} disconnected. Choose the edge {v,w}\{v, w\}{v,w} , the vertex xxx and a component CCC of G−{x,v,w}G - \{x, v, w\}G−{x,v,w} with ∣V(C)∣|V(C)|∣V(C)∣ minimal. Then xxx has a neighbor yyy in CCC , and (as G/{x,y}G/\{x, y\}G/{x,y} is not 3-connected) there is…

    DDD contains a neighbor ddd of yyy , so d∈V(C)d \in V(C)d∈V(C) and DDD is a subgraph of CCC ; as y∈V(C)∖V(D)y \in V(C) \setminus V(D)y∈V(C)∖V(D) , DDD is a smaller such component (for the edge {x,y}\{x, y\}{x,y} and the vertex zzz ). If DDD had no neighbor of yyy , it would be a component of G−{x,z}G - \{x, z\}G−{x,z} , contradicting 3-connectivity. D⊆CD \subseteq CD⊆C because DDD is connected, avoids x,v,wx, v, wx,v,w , and meets CCC .

65. [Kuratowski-Wagner Theorem] Kuratowski, Wagner, 3-connected version. When is a 3-connected graph planar?

    If and only if it contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a minor. The notes refer to Korte and Vygen for the proof.

66. [Kuratowski-Wagner Theorem] Lemma (Thomassen). GGG has at least five vertices, is not 3-connected, and contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a minor. What can you add to GGG ?

    An edge between two non-adjacent vertices v,wv, wv,w such that the new graph still contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a minor. The notes refer to Korte and Vygen for the proof.

67. [Kuratowski-Wagner Theorem] Kuratowski-Wagner Theorem. When is a graph planar?

    If and only if it contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a minor.

68. [Kuratowski-Wagner Theorem] Kuratowski-Wagner Theorem: a graph is planar if and only if it contains neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a minor.Why does a planar graph contain neither as a minor?

    Minors of planar graphs are planar, and K5K_5K5​ and K3,3K_{3,3}K3,3​ are not planar.

69. [Kuratowski-Wagner Theorem] Known: (1) a 3-connected graph is planar if and only if it has neither K5K_5K5​ nor K3,3K_{3,3}K3,3​ as a minor. (2) If GGG has ≥5\ge 5≥5 vertices, is not 3-connected and has neither as a minor, an edge can be added between two non-adjacent vertices keeping neither as a minor.How do these prove that a graph GGG without K5K_5K5​ and K3,3K_{3,3}K3,3​ minors is planar?

    Keep adding edges by (2) until the graph is 3-connected; by (1) that graph is planar, so its subgraph GGG is planar. If GGG is already 3-connected, (1) applies directly.

70. [Kuratowski-Wagner Theorem] Kuratowski's original 1930 version of the planarity theorem used subdivisions instead of minors; the minor version is due to Wagner (1937).

71. [Kuratowski-Wagner Theorem] GGG is a connected planar graph with a fixed planar embedding, and G∗G^*G∗ is its planar dual with standard embedding. What is (G∗)∗(G^*)^*(G∗)∗ ?

    GGG (up to isomorphism).

72. [Kuratowski-Wagner Theorem] The planar dual G∗G^*G∗ of an embedded planar graph GGG has the faces as vertices and one edge e∗e^*e∗ per edge eee of GGG , joining the faces on the two sides of eee . In its standard embedding, Je∗J_{e^*}Je∗​ crosses JeJ_eJe​ exactly once and touches nothing else of the drawing of GGG .Why does every face of the standard embedding of G∗G^*G∗ contain at least one vertex point ψ(v)\psi(v)ψ(v) of GGG ?

    The boundary of a face FFF of G∗G^*G∗ contains some dual edge Je∗J_{e^*}Je∗​ , and FFF contains ψ(v)\psi(v)ψ(v) for an endpoint vvv of eee . This is one half of the proof that (G∗)∗=G(G^*)^* = G(G∗)∗=G .

73. [Kuratowski-Wagner Theorem] The planar dual G∗G^*G∗ of an embedded planar graph GGG has the faces as vertices and one edge e∗e^*e∗ per edge eee of GGG , joining the faces on the two sides of eee . In its standard embedding, Je∗J_{e^*}Je∗​ crosses JeJ_eJe​ exactly once and touches nothing else of the drawing of GGG .Every face of the standard embedding of G∗G^*G∗ contains at least one vertex point of GGG .For connected GGG , why does every face contain exactly one?

    By Euler's formula G∗G^*G∗ has ∣E(G∗)∣−∣V(G∗)∣+2=∣E(G)∣−(∣E(G)∣−∣V(G)∣+2)+2=∣V(G)∣|E(G^*)| - |V(G^*)| + 2 = |E(G)| - (|E(G)| - |V(G)| + 2) + 2 = |V(G)|∣E(G∗)∣−∣V(G∗)∣+2=∣E(G)∣−(∣E(G)∣−∣V(G)∣+2)+2=∣V(G)∣ faces. ∣E(G∗)∣=∣E(G)∣|E(G^*)| = |E(G)|∣E(G∗)∣=∣E(G)∣ , and ∣V(G∗)∣|V(G^*)|∣V(G∗)∣ is the number of faces of GGG . So the faces of G∗G^*G∗ correspond to the vertices of GGG , and (G∗)∗(G^*)^*(G∗)∗ is isomorphic to GGG .