# CPTS 553 Graph Theory Assignment 7 solution

\$24.99

Category:

## Description

5/5 - (4 votes)

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.
π
π
π
π
π
π
π
π