- Thread starter
- #1

https://www.dropbox.com/s/vq8rk6z5ea5gpwd/Problems.docx

- Thread starter repoman
- Start date

- Thread starter
- #1

https://www.dropbox.com/s/vq8rk6z5ea5gpwd/Problems.docx

- Jan 30, 2012

- 2,589

I'll give some hints about problem 1. For A, answer the following questions.

- How many (unordered) pairs of vertices does a graph with $n$ vertices have? Let's denote this number by $C(n)$.
- If a graph $G$ has $e$ edges, how many edges does the complement of $G$ have? Make sure you know what a graph complement is. The answer should use $C(n)$.
- What can be said about the number of edges in isomorphic graphs?
- Suppose a self-complementary graph with $n$ vertices has $e$ edges. Write an equation on $e$ using the definition of a self-complementary graph and points 2 and 3 above.

For B, draw a graph connecting each pair of vertices using either solid or dashed line. The number of edges of each type should be what you found in point A. The solid graph should be isomorphic to the dashed one. Put 4 vertices in the corners of a square. Make it so that rotating the picture by 90 degrees maps solid edges into dashed ones and vice versa. For 5 vertices, prove that a regular pentagon is self-complementary (construct an explicit bijection between vertices and check that it is an isomorphism).

For C, use the fact that $C(n)$ is an integer.