Problem 3
Find a graph \(G\) such that \(\bar{G}\) is not connected.
Problem 4
Construct all degree sequences for graphs with four vertices and no isolated vertex.
Problem 4
Prove that a tree is a bipartite graph.
Problem 5
Determine all possible degree sequences for graphs with five vertices containing no isolated vertex and six edges.
Problem 5
Let \(G=(V, E)\) be a connected graph with at least two vertices. Prove that if \(|V|>\) \(|E|,\) then \(G\) has a vertex of degree one.
Problem 6
Determine all possible degree sequences for graphs with five vertices containing no isolated vertex and eight edges.
Problem 6
Prove that if \(C_{1}, C_{2}, \ldots, C_{k}\) is a sequence of cycles in a directed graph \(D\) such that every two consecutive cycles have at least one common vertex, then the subgraph determined by the union of these cycles is strongly connected.
Problem 6
Let \(T\) be a tree. Prove that if an edge \(e\) joins two nonadjacent vertices in \(T,\) then \(T \cup\) [e\\} contains a cycle.
Problem 7
Let \(G\) be a connected graph with average degree greater than two. Prove that \(G\) contains at least two cycles.
Problem 7
Prove that any tree with two or more vertices has at least two vertices of degree one.
