1. Draw the below graphs and then write the size, order, deg(v), adj(v), of each graph. (and deg.(v), deg (v) for the directed graphs) 2. Provide formulas for both the order and size of Qn.Explain. The graph Qn, n 2 1, has vertex set equal to the set of all binary strings of length n. Moreover, two vertices are adjacent if they differ in at most one bit place. For example, in Q3, 000 is adjacent to 010, but not to 011. Draw Q1, Q2, and Q3. Show that Q3 has a Hamilton cycle, (a cycle that visits all the vertices exactly once). 3. Consider the directed graph where vertices are reachable tic-tac-toe board positions and edges represent valid moves. What are the in-degree and out-degree of the fallowing vertex? (It is O's turn) 4