# CPTS553 Assignment 7 Solved

30.00 \$ 15.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## Description

Rate this product

Assignment 7

Questions with a (⋆) are each worth 1 bonus point for 453 students.

1. Some questions about drawing 𝑄𝑘 graphs on surfaces. A. Show that 𝑄3 can be drawn on the plane.
1. Use the fact that 𝑄4 is bipartite and a total edge count argument to show that 𝑄4 cannot be drawn on the plane.
2. Draw 𝑄4 on the torus (use the 𝑎𝑏𝑎−1𝑏−1 square representation drawn below). HINT:  𝑄4 is isomorphic to 𝐶4 × 𝐶4.

1. Show that 𝑔(𝑄5) ≥ 5. Recall that for 𝑄5 we have 𝑛 = 32 and 𝑚 =
2. 80. As a first step, use a total edge count argument to show that

𝑟 ≤ 40.  Feed this information into Euler’s formula  𝑛 − 𝑚 + 𝑟 = 2 − 2 𝑔(𝑄5).

1. (⋆) Generalize the strategy in part D to obtain a “meaningful” lower bound for 𝑔(𝑄𝑘).  Here, recall that 𝑛 = 2𝑘 and 𝑚 = 𝑘2𝑘−1.

1. The Petersen graph 𝑃 is depicted:
2. Use a total edge count argument to show that 𝑃 is non-planar. You may use the fact that 𝑃 has no triangles or 4-cycles as subgraphs. B. Draw 𝑃 on a torus without the edges crossing.

1. Draw 𝐾4,4 on a torus without the edges crossing. Suggestion:  Start with your two partite sets (every edge joins a red vertex to a blue vertex) arranged as shown: