Skip to content

Homework 9

  1. Let \(A\) be a convex polygon. Polygon \(A\) is divided into triangles by drawing non-intersecting diagonals. How many triangles are formed if

    • \(A\) is a 17-gon;
    • \(A\) is a 33-gon;
    • \(A\) is a \(2^n + 1\)-gon ?

    Let's use induction.
    Base case:
    ​\(n=3, v=3, e=3+0, f=2-v+e=2, \#\Delta=f-1=1\)
    ​\(n=4, v=4, e=4+1, f=2-v+e=3, \#\Delta=f-1=2\)
    ​\(n=5, v=5, e=5+2, f=2-v+e=4, \#\Delta=f-1=3\)

    Claim: There are \(n\) vertices, \(2n-3\) edges, \(n-1\) faces, \(n-2\) triangles in an \(n\)-polygon.
    Suppose this is true for \(n=k\), then for \(n=k+1\).

    image​

    In this process, \(v=k+1\), \(e=2k-3+2-1+1=2k-1=2{(k+1)}-3\)
    Then \(f=2-v-e=(k+1)-1\), then we have \((k+1)-2\) triangles
    Thus proposition holds for all \(n\).
    ① If A is a 17-gon, then we have 15 triangles
    ② If A is a 33-gon, then we have 31 triangles
    ③ If A is a \(2^n+1\)-gon, then we have \(2^n-1\) triangles

  2. A triangle-free graph is a plane graph whose faces are not triangles.

    • Prove that for a triangle-free plane graph with \(n \ge 3\) vertices, the inequality \(2e \ge 4f\) holds.
    • Prove that a triangle-free plane graph with \(n \ge 3\) vertices has at most \(2n - 4\) edges.
    • Prove that \(K_{2,n-2}\) has exactly \(2n - 4\) edges and is planar.

    ① We know the face must have more than 4 edges to form, otherwise it will have a triangle face(\(*\)).
    Then consider the pair of face and edge: \((F,E)\)
    ​\(\#(F,E)=2e\) since each edge can separate two faces. And \(\#(F,E)\ge4f\) since \((*)\).

    Then \(2e\ge4f\)
    ② Since \(v-e+f=2\), then \(f=2+e-n\), since \(2e\ge4f\), then \(2e\ge8+4e-4n\), then \(e\le2n-4\)
    ③ image​

    Consider the pair \((V_i, U_j)\), \(\#(V_1, U_j)=n-2\) where \(j\in[1,n-2]\) and \(\#(V_2, U_j)=n-2\)
    Then \(\#(V_i, U_j)=\sum_{i=1}^2 \#(V_i, U_j)=2n-4\)
    And the pair of two vertices is exactly the edge. Thus \(e=2n-4\).
    Since \(K_{2,n-2}\) has one set of two vertices, thus it is not minor of \(K_{3,3}\) and \(K_5\).
    Thus \(K_{2,n-2}\) is planar by theorem

  3. 20 points are drawn inside the octagon. Some of these points, as well as the corners of the octagon, were connected using straight segments so that the octagon had been partitioned into quadrilaterals. Every arc of the resulting subdivision separates two regions (this condition is redundant and follows from the hypothesis). How many quadrilaterals were obtained?

    We have \(20+8=28\) vertices and \(f=1+q\).
    Consider \(\#(F,E)=2e\) and \(\#(F,E)=4f+4\) where \(4\) is the outer face with additional edges.
    Then \(2e=4f+4=8+4q \Rightarrow e=4+2q\).
    Then \(v-e+f=2 \Rightarrow 28-4-2q+1+q=2\).
    Then \(q=23\).

  4. In a connected plane graph all the vertices are of degree 3 and belong to exactly three faces. All the faces of this graph, including the exterior one, are either pentagons or hexagons. Every arc of the graph separates two faces. How many pentagons are there?

    By shakinghand lemma: \(\sum_{v\in V}\text{deg}(v)=2e=3\cdot v\Rightarrow v=\frac{2}{3}e\) since all the vertices are of degree 3

    Assume there are \(p\) pentagons and \(f-p\) hexagons.
    Then \(\#(F,E) = 2e = 5p + 6(f-p)\). Then \(2e = 6f - p\)

    Since \(v - e + f = 2\), then \(\frac{2}{3}e - e + f = 2\). Then \(3f - e = 6\) and \(e = \frac{6f - p}{2}\)
    Then \(3f - 3f + \frac{p}{2} = 6\), then \(p = 12\)