# 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: