Starting from:
$30

$24

Graph Theory Assignment 7 Solution

    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, = (92) = 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.

More products