Graph Theory Problems and Solutions

Word Graphs with Exactly Six Vertices and Nine Edges

1. A word graph is a graph where the vertices are three-letter English words and two words are adjacent if and only if they have a different first, second or third letter but the same letter in the other two positions. Draw a word graph with exactly six vertices and exactly nine edges. Label the vertices with the corresponding words but no further justification is needed.

2. A busy university administrator is asked to attend 216 meetings. Each meeting starts on the hour and lasts one hour. Not surprisingly, there are a total of  pairs of meetings that conflict. Every meeting conflicts with at least one other meeting but there are never more than four meetings scheduled at the same time. Half of the meetings conflict with exactly two other meetings. At how many times are four meetings scheduled? Prove that your answer is correct.

3. What is the maximum possible number of edges in a graph with six vertices and less than two 3-cycles? Prove that your answer is correct.

4. In a department of six people, some pairs of people are compatible and the other pairs are not. Prove that it is possible to form a committee of three people from this department such that all pairs of people on the committee are compatible or all pairs of people on the committee are not compatible.

5. A city's new light rail system consists of n stops. The world's worst urban planner is hired to determine when stops are joined by bi-directional tracks. The planner flips a coin for each pair of distinct stops. For each flip, if the coin comes up heads, the two stops are directly joined by a track and otherwise they are not directly joined by a track. If more than  different rail systems can be created in this way, what is the smallest possible value of n? Justify your answer. 

6. Prove there exists a regular graph with vertices and 24 edges that is not isomorphic to the graph below.

7. (a) Prove that every 2-regular graph consists of disjoint cycles.

(b) Draw as many 2-regular graphs on 8 vertices as possible such that no two are isomorphic. No justification is necessary.

(c) How many 2-regular graphs are there with vertices V = (a, b, c, d, e, f,g,h) and unequal sets of edges? Full marks will be awarded for a correct final answer without explanation but part marks may be possible for an incorrect final answer with a very brief explanation.

8. For two graphs G and H define C oa H to be the graph with vertices V (G) x V (H) where distinct vertices (x1,91) and (x2, y2) are adjacent if and only if xi = x2 and {yi, y2} E E(H) or yi = y2 and {xi, x2} E E(G). Prove or disprove each of the following. (a) If C and H are complete, then G ca H is complete. (b) If C and H are regular, then Goa H is regular.