Description
Problem 1: Prove that a self-complementary simple graph with n vertices exists if and only if n ≡ 1 mod 4 or n ≡ 0 mod 4. (Hint, generalize problems 5 and 6 from the class.)
Problem 2: Let P and Q be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
Problem 3: Prove that the following assertions are equivalent for a graph T: (i) T is a tree
- any two vertices of T are linked by a unique path in T
- T is connected but T − e is disconnected for every edge e of T
- T does not contain a cycle but T + xy contains a cycle for any two non-adjacent vertices x,y of T.
Problem 4: Use induction on the size or structure of T to prove that if T is a tree and G is any graph with δ(G) ≥ |T|−1, then T ⊆ G. |T| is the number of vertices of T, δ(G) is the smallest vertex degree in G, and T ⊆ G means we can create an isomorphic copy of T by deleting vertices and edges of G.
