Assignment
Q1: Hypercube graph Q5. Can you generalize to Qn?
Q2: The Petersen graph?
Q3: Two opposite corners are removed from an 8-by-8 checkerboard. Prove that it is impossible to cover the remaining 65 squares with 31 dominoes, such that each domino covers two adjacent squares?
Q4: Find all possible isomorphism types of the given kind of simple graph?
Q5: Draw a forest having ten vertices, seven edges, and three components?
Q6: Find all the cut-vertices and cut-edges in this graph below?
Q7: Draw a 5-vertex connected graph G that has no cut-vertices, and then verify that G satisfies each of the following properties.
a. Given any two vertices, there exists a cycle containing both.
b. For any vertex v and any edge e of G, there exists a cycle containing v and e.
c. Given any two vertices x and y, and any edge e, there exists a path from x to y that contains e.
d. Given any two edges, there exists a cycle containing both.
e. Given any three distinct vertices u, v, and w, there exists a u-v path that contains w.
f. Given any three distinct vertices u, v, and w, there exists a u-v path that does not contain w.
Q8: Determine whether the graphs in the given pair are isomorphic?
Q9: Draw a digraph that has the given adjacency matrix?
Q10: Cartesian product of two graphs (psedocode)?
Q11: Decide which pairs of these three graphs are isomorphic.
Q12: An 8-vertex, 2-component, simple graph with exactly 10 edges and three cycles?
Q13: An 11-vertex, simple, connected graph with exactly 14 edges that contains five edge-disjoint cycles?
Q14: Prove or disprove: If a simple graph G has no cut-edge, then every vertex pf G has even degree?
Q15: Prove that if a graph has exactly two vertices of odd degree, then there must be a path between them?
Q16: Show that any nontrivial simple graph contains at least two vertices that are not cut-vertices?
Q17: Draw the specified tree(s) or explain why on such a tree(s) can exist?
- A 14-vertex binary tree of height 3.
Q18: Prove that a directed tree that has more than one vertex with in degree 0 cannot be a rooted tree?