♠ Let G be a 6-regular connected graph with 24 vertices. Prove that G cannot be planar.
Now let G be a k-regular connected graph with n vertices. Determine the values of k and n for which: G must be non-planar; G might be planar or non-planar; G must be planar. (For example, what if k = n-1? What if k = 1?) Give as complete an answer as you can.
Keep in mind Euler's Theorem n - m + r = 2 for a connected planar graph, and the basic inequalities:g r ≤ ∑R deg(R) ≤ 2m ,where G is planar with n vertices, m edges, r regions; g is the girth of G (length of the shortest cycle); and deg(R) means the number of edges in the boundary of R.Use the basic theory in the HHM chapter on planar graphs.