(Solved): 1. The \( \mathrm{n} \)-cube, denoted by \( Q_{n} \), is the graph that has \( 2^{n} \) vertices r ...

1. The \( \mathrm{n} \)-cube, denoted by \( Q_{n} \), is the graph that has \( 2^{n} \) vertices representing the bit strings of length \( \mathrm{n} \). Two vertices are adjacent if they differ in exactly one-bit position (bit flip). Show by example that for \( Q_{2} \) and \( Q_{3} \) (see figure below), the minimum number of vertices to remove to cause the graph to become disconnected is \( n \). (2pts) 2. Using the graph \( Q_{3} \) write one distinct and nontrivial example for each of the following: trail, path, closed walks, circuits, simple circuits. (1 pts) 3. For which values of \( n \) can an \( \mathrm{n} \)-cube have an Eulerian circuit? (1pt)