1

• $V(G(k))=\{ (x_i){i=1}^{2k} : x_i \in \mathbb{N} , \sum{i=1}^{2k} x_i \in \{k,k+1\} \}, |V(G(k))|={2k \choose{k}} +{2k \choose{k+1}}$
• According to the definition of a cube, $G(k)$ is a bipartite graph with orders ${2k \choose{k}}, {2k \choose{k+1}}$ on each side. Every vertex on the left has a degree $k$, while every on the right has a degree $2k-(k-1)=k+1$, therefore $|E(G(k))| = ({2k \choose k} k + {2k \choose k+1} (k+1))/2 = (\frac{(2k)!}{k! (k-1)!} + \frac{(2k)!}{k! (k-1)!} )/2=\frac{(2k)!}{k! (k-1)!}$.
• The girth is 6. It’s a biparite graph so there is no odd-length cycle. Length 2 is impossible for cycle. 4 is also impossible because it means that two vertices on one side have two different paths of length 2 between them, and therefore two different ways to change a binary tuple to another by switching twice, which is impossible. On the other hand, 6 can be achieved by taking

$$ (\dots, 1, \dots, 0, \dots, 0, \dots) - \\ (\dots, 1, \dots, 1, \dots, 0, \dots) - \\ (\dots, 0, \dots, 1, \dots, 0, \dots) - \\ (\dots, 0, \dots, 1, \dots, 1, \dots) - \\ (\dots, 0, \dots, 0, \dots, 1, \dots) - \\ (\dots, 1, \dots, 0, \dots, 1, \dots) - \\ (\dots, 1, \dots, 0, \dots, 0, \dots) $$

• The degree of vertices, as mentioned, is $k$ on one side and $k+1$ on the other side.

2

(a)

It suffices to show that every connected graph has a closed walk that traverses each edge exactly twice. This can be done by induction.

• Base case: a connected graph with order 1 satisfies the property.
• Induction: Suppose every connected graph with order k-1 satisfies the property. Now for every connected graph $G’$ with order k, pick any vertex v. Construct $G=G’ - v$, which satisfies the property. Now consider each edge connecting v to $G$, say $\{ v,w \}$ where $w \in V(G)$. Now say the closed walk of $G$ that traverses each edge exactly twice is $\dots w \dots$, then we turn it into $\dots w, (w,v), v, (v,w), w \dots$ By repeating this process on every edge connecting v to $G$, we obtain a closed walk of $G’$ that traverses each edge exactly twice.

Another method is Depth-First Search.

Another method is constructing a graph that doubles the edges between every pair of vertices and therefore must have an Euler circuit.

(b)

Constructing a graph G’ based on graph G that triples the edges between every pair of vertices. The $deg_{G'}(v) = 3 deg_G(v)$ and therefore G’ has an Euler circuit if and only if G has an Euler circuit. Then we can disprove this statement by picking a connected graph with no Euler circuit, according to Euler’s Theorem.

3

The size of a maximum independent set in the Petersen Graph is 4, as illustrated below since no set with size 5 is an independent set. The number of maximum independent sets is 5. This is because to obtain an independent set with size 4, the set must include two vertices in the outer cycle, which has 5 choices. Once this is settled, the choice of two inner vertices is fixed.

5

(left)