MHB What Are Key Strategies for Solving Discrete Math Graph Theory Problems?

[repoman1]

I have these problems I need help with. Can anyone take a look at them?

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

 

[Evgeny.Makarov]

First, I'd like to point out http://www.mathhelpboards.com/misc.php?do=vsarules #8: "Do not ask more than two questions in a post" and rule #11: "Show some effort". I recommend starting separate threads for problems 2–5 and describing what you have done and/or what difficulty you are having.

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

1. How many (unordered) pairs of vertices does a graph with $n$ vertices have? Let's denote this number by $C(n)$.
2. 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)$.
3. What can be said about the number of edges in isomorphic graphs?
4. 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.