Skip to content

5.21 Plane and Planar Graph

  1. The graph \(G\) has six vertices, the degree of every vertex is 4. Is \(G\) planar?

    1. If \(G\) is not connected, connected component:

      1. 5 and 1

        image​If this component is a complete graph on 6 vertices, this is not planar since it has minor graph of \(K_5\)

        image​

        But if 5 is not \(K_5\), then it's possible to be a planar since \(K_{5}\) is not a minor since the edges are same, so we can always find. Also, \(K_{3,3}\) is always impossible since its vertices greater than 5 2. If no connected component of size \(\geq 5\)--always possible since Theorem(Kuratowsi) 2. If \(G\) is connected

      If it has minor \(K_{3,3}\), then impossibleimage​

      But it's possible, to construct, we know \(v-e+f=2\Rightarrow 6-12+f=2\) by handshaking lemma

      Then \(f=8\), image, this is a planar since it's can be drawn on the plane, then it's a plane graph, then it's planar

  2. Prove that any connected graph of 10 vertices, and all degrees at least 5 is not planar.

    For such graphs, for planarity we need \(3v-6\geq e\) and \(\sum\deg \geq 50\Rightarrow e\geq 25\)​

    But \(3v-6=24\), contradiction

  3. Seven lakes are connected with 10 non-intersecting channels. How many islands are there?

    Island is the bounded face, lakes are vertices and channels are edges

    Then \(7-10+f=2\), then \(f=5\) but this including the exterior one, then we have \(4\) islands

    But it's possible that we have isolate componentimage​

    Thenimage, We add a edge to connect them, then \((v_{1}+v_{2})-(e_{1}+e_{2})-1+(\text{total number of faces})=2\)

    The whole part is \(v - e + f -1= 2\), \(-1\) since they share the same outside face

    Induction: \(v - e + f = C + 1\)

    \(C\) - # Connected components

    \(7-10+f=C+1\), then \(f=C+4 \,\,\,s.t.\,\,\, \text{\#islands}=C+3\) for \(1\leq C \leq 7\)

  4. 20 points a drawn inside the square. Some of these points, as well as the corners of the square, were connected using straight segments, so that the square had been partitioned into triangles. How many triangles were obtained?

    We have 24 vertices and \(f=1+t\), consider \(3f+1=\#(F,E)=2e\) where \(1\) is the outside edge

    Then \(24-\frac{3t+4}{2}+(1+t)=2\), then \(t=42\)

  5. A graph \(G\) is properly colored, if any two adjacent vertices have different colors. Prove, that any planar graph admits a proper coloring in 6 colors.

  6. How many ways are there color the vertices of graph \(G\) in \(t\) colors, if a) \(G = P_n\), b) \(G = K_n\), c) \(G\) is a general graph.