You may select any five theorems from this list for your proof portfolio, so long as you also cover all five methods of proof required for the portfolio. I will add theorems to the list as the course progresses, and you may also request additions.
Each theorem is labeled with one or more bracketed letters that suggest suitable proof methods. Although your proof portfolio requires five different methods, there is a sixth method here. You can count this sixth method, proof by algorithm, as a special kind of direct proof for your portfolio. The following table shows the correspondence between code letters and methods of proof:
| A | Algorithm |
| C | Contradiction |
| D | Direct Proof |
| I | Induction |
| K | Cases |
| P | Contrapositive |
I have largely adapted this list from one San Skulrattanakulchai prepared for a previous course offering; I appreciate his permission.
Prove the Pigeonhole Principle on page 384 of CZ. [C]
Prove Ramsey's Theorem on page 384-385 of CZ. [C]
Prove Theorem 1.6 on page 12 of CZ by induction. [I and optionally K]
Two nontrivial graphs G and H are both bipartite if and only if their Cartesian product graph G × H is bipartite. [D, P]
Prove that a graph is a cycle graph if and only if it is 2-regular and connected. [D, A]
(CZ, Exercise 1.17(a)) Prove that if P and Q are two longest paths in a connected graph, then P and Q have at least one vertex in common. [C]
(CZ, Exercise 1.16) Let P : u=v0, v1, ..., vk=v, k ≥ 1, be a u-v geodesic in a connected graph G. Prove that d(u, vi) = i for each integer i with 1 ≤ i ≤ k. [D, C, I]
(CZ, Exercise 2.10(b)) Let G be a graph of order n. Prove that if deg u + deg v ≥ n - 2 for every pair u, v of nonadjacent vertices of G, then G has at most two components. [P or C]
(CZ, Exercise 2.12) Prove that if G is a graph of order n such that Δ(G) + δ(G) ≥ n-1, then G is connected and diam(G) ≤ 4. Show that the bound n-1 is sharp. [D]
(CZ, Exercise 2.15) A certain connected graph G has the property that for every two vertices u and v of G, the length of each u-v path is even or the length of each u-v path is odd. Prove that G is bipartite. [D and C]
Prove that for all integers r ≥ 1 and k ≥ 2, any r-regular, complete k-partite graph Ks1, s2, ..., sk has s1 = s2 = ... = sk. [I]
Prove that G is a complete bipartite graph if and only if G is nontrivial, connected, and does not contain C3 or P4 as a vertex-induced subgraph. [P or C, D]
(CZ, Exercise 3.12) Let G and H be two self-complementary graphs with disjoint vertex sets, where H has even order n. Let F be the graph obtained from G ∪ H by joining each vertex of G to every vertex of degree less than n/2 in H. Show that F is self-complementary. [D]
(CZ, Exercise 3.27) Prove that Aut(G) and the automorphism group of the complement of G are isomorphic for every graph G. [D]
Prove that for any graph automorphism α, there exists a nonnegative integer k such that αk = ε, where ε is the identity automorphism. (Do not prove this simply by noting that the automorphisms form a group and citing the corresponding general theorem about groups.) [C and I]
Show that any nontrivial tree T has at least Δ(T) leaves. [D or I]
Prove Exercise 4.8 on page 92 of CZ by induction. [I]
Prove the theorem stated in Part (b) of Exercise 4.12 on page 93 of CZ: There exists no tree T containing two distinct edges e1 and e2 such that the two components of T − e1 are isomorphic and the two components of T − e2 are isomorphic. [C]
Prove Exercise 5.6 on page 110 of CZ. [D, C, K]
Prove Exercise 5.7 on page 111 of CZ by algorithm and contradiction. [A, C]
(CZ, Exercise 5.10) Prove that a connected graph G of size at least 2 is nonseparable if and only if any two adjacent edges of G lie on a common cycle of G. [D, P or C]
Prove that a nontrivial connected graph G has a closed spanning walk that contains every edge of G exactly three times if and only if G is eulerian. [D]
Do the proof in CZ Exercise 6.6, but corrected by adding the additional premise that G is nontrivial. [D]
Prove that for any graph G, there exists some Eulerian graph H such that G is an induced subgraph of H. [D and optionally K]
Let G be a nontrivial, regular, connected graph of even order such that its complement graph is also connected. Show that either G or its complement graph is Hamiltonian. [D, C]
Prove that for all n ≥ 2, the hypercube Qn is hamiltonian. [I]