[SOLVED] CPTS553-Assignment 7 Solved

Description

1. Show that 𝐾₈ can be drawn on a 2-holed torus without edges crossing. Feel free to use the octagon model as a framework for youre drawing:
2. Use an edge-counting argument to show that 𝐾₉ cannot be drawn on a

2-holed torus without edges crossing.  Ingredients:  For 𝐾₉, you have

9

𝑛 = 9, 𝑚 = ( ) = 36.  What would 𝑟 have to be?  What is a lower 2

bound on the total edge count since every region must be bounded by at least three edges?

3. If we re-orient the arcs around the diagram from #1 so they all point clockwise, what is the resulting value of 𝑛 − 𝑚 + 𝑟?

4. In terms of 𝑛 ∈ {2,3,4,5,6, … }, how many tournaments are there with the node set 𝑁 = {1,2,3, … , 𝑛}? This is equivalent to asking for how many ways are there to orient the edges of 𝐾_𝑛 with vertex set {1,2,3, … , 𝑛}.

5. Let 𝑛 ∈ {3,4,5,6, … } be fixed. Show that there are exactly two orientations of 𝐶_𝑛 with vertex set 𝑉 = {0,1,2, … , 𝑛 − 1} that are strongly connected.