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: