[Solved] CSDS455 Homework1

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.