CPTS 553 Graph Theory Assignment 7 solution

Description

1. Show that 𝐾8 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 𝐾9 cannot be drawn on a
2-holed torus without edges crossing. Ingredients: For 𝐾9
, you have
𝑛 = 9, 𝑚 = (
9
2
) = 36. What would 𝑟 have to be? What is a lower
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.
𝑎
𝑎
𝑏
𝑏
𝑐
𝑑
𝑑
𝑐