6200 Exam

1. Describe the number(s) p for which a (p,p) graph can exist. Explain.
2. Which of the following degree sequences is a graphical sequence? For each which is not, explain why not. For the ones that are, construct graphs with the degree sequences.
   1. 3, 3, 3
   2. 3, 3, 3, 3
   3. 3, 3, 3, 3, 1
   4. 3, 3, 3, 3, 1, 1
3. Demonstrate that a graph G has the property that every component is complete if and only if G^C is a complete bipartite graph.
4. Determine whether each of the following is true or false. Show reasoning.
   • The union of two trees is a tree
   • The join of two trees is a tree
   • The product of two trees is a tree
   • If G is connected then G^C is not connected
   • If G is a tree then G^C is not a tree