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

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
Physics news on Phys.org
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.