Problem 1
Construct connected graphs of the following sorts: (a) All graphs of five vertices with at least seven edges (b) All cubic graphs with at most eight vertices (c) One 4 -regular graphs of six vertices (d) Three 5 -regular graphs of eight vertices
Problem 1
Find a graph with 12 edges having six vertices of degree three and the remaining vertices of degree less than three.
Problem 1
Construct all trees on six vertices. Find an algorithm for constructing all possible trees on six vertices if you know all possible trees on five vertices.
Problem 2
If the sequence \(d_{1}, d_{2}, \ldots, d_{n}\) of nonnegative integers represents the degrees of the vertices of a tree with \(n\) vertices, then \(\sum_{i=1}^{n} d_{i}=2(n-1)\). Show that the converse is false.
Problem 2
Let \(D\) be a directed graph with an outdegree of each vertex of at least one. Prove that \(D\) contains a directed cycle. Show that the same result holds if the hypothesis is that each node has an indegree of at least one.
Problem 2
In a graph, the edges are pairs of vertices, with no ordering - unlike our formalization with relations as sets of ordered pairs. So, here treat the edges as ordered pairs as follows: For any graph \(G=(V, E),\) let \(\hat{E}\) be the set of all ordered pairs \(\left(v_{1}, v_{2}\right)\) and \(\left(v_{2}, v_{1}\right)\) where \(\left(v_{1}, v_{2}\right) \in E .\) Show that \(C O N N\) is the reflexive and transitive closure of \(\hat{E}\).
Problem 2
Give an example of a graph with at least four vertices, or prove that none exists, such that: (a) There are no vertices of odd degree. (b) There are no vertices of even degree. (c) There is exactly one vertex of odd degree. (d) There is exactly one vertex of even degree. (e) There are exactly two vertices of odd degree.
Problem 3
Prove that any directed acyclic graph contains at least one vertex with an indegree of zero. Use this result to devise a different algorithm to do a topological sort.
Problem 3
Find a graph \(G\) such that \(\bar{G}\) is not connected.
Problem 3
Let \(G\) be a tree with all vertices having odd degree. Prove that \(G\) contains an odd number of edges. Show that this is not true if \(G\) is not a tree.
