CSDS 455: Applied Graph Theory
Homework 1
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
(ii) any two vertices of T are linked by a unique path in T
(iii) T is connected but T − e is disconnected for every edge e of T
(iv) 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.
