A planar graph is a graph that can be drawn in a plane without any two edges intersecting....

A planar graph is a graph that can be drawn in a plane without any two edges intersecting.

a. Show that neither of the graphs in Figure 1 is planar.

---

b. Show that in a planar graph, there must exist some vertex which is connected to no more than five nodes.

---

c. Show that in a planar graph, |E| ≤ 3|V| − 6.

Figure: Graph used in Exercise