Problem 7
Prove that if a graph \(G\) contains an Eulerian circuit, then \(G\) is orientable.
Problem 7
Let \(G\) be a connected graph with average degree greater than two. Prove that \(G\) contains at least two cycles.
Problem 8
Prove that a graph \(T\) is a tree if and only if \(T\) is connected but the deletion of any edge disconnects \(T\).
Problem 9
For \(n=2,3,4,5,\) determine a relationship between the number of edges and the number of vertices in an \(n\) -regular graph with \(p\) vertices where \(p=1,2,3, \ldots .\) Construct all 3-regular graphs on four and six vertices.
Problem 9
Prove that a cycle and the complement of any spanning tree must have at least one edge in common.
Problem 9
Prove that a connected undirected graph is orientable if and only if each edge is contained in a cycle.
Problem 10
Show that any graph with a Hamiltonian cycle is orientable.
Problem 10
Let \(T_{1}\) and \(T_{2}\) be two spanning trees of a graph \(G\). Prove that if \(a\) is any edge in \(T_{1}\). then there exists an edge \(b\) in \(T_{2}\) such that the graph obtained from \(T_{1}\) by replacing \(a\) with \(b\) is a spanning tree of \(G\).
Problem 10
Let \(G\) be a graph. Prove that \(G\) is bipartite if and only if \(G\) contains no odd cycle.
Problem 11
Prove that a graph \(G\) is connected if and only if \(G\) contains a spanning tree.
