There are $2$ possibilities for each of the $k$ coordinates of a vertex, so there are $2^k$ vertices in total.
Each vertex has $k$ neighbours (why?) so the sum of the degrees of all the vertices is $k2^k$. But this counts each edge twice, so...
To show that the graph is bipartite, consider the coordinate sum of a vertex. If this sum is even, what can you say about the sums for neighbouring vertices? What if the sum is odd?
The algorithm is: pick an edge $x y_1$. Inductively find a $\Delta+1$ colouring $\phi$ of $G \setminus \{ x \to y_1 \}$.
For every vertex, there is a colour which is not used at that vertex, because the degree of the vertex is $\leq \Delta$ but we have $\Delta+1$ colours to choose from.
Let $c$ be a colour missing from vertex $x$, and $c_1$ missing from $y_1$.
Then if $c_1$ is missing at $x$, we are done: colour the edge $x y_1$ with colour $c_1$.
Otherwise, $c_1$ is not missing at $x$, so there is some $y_2$ in the neighbourhood $\Gamma$ of $x$ with $\phi(x \to y_2) = c_1$.
Repeat: given $y_1, \dots, y_k \in \Gamma(x)$ distinct, and distinct colours $c_1, \dots, c_k$ such that $c_i$ is missing at $y_i$ for all $i$, and $\phi(x y_i) = c_{i-1}$, do the following: if $c_k$ is missing at $x$, stop and recolour $x y_i$ with colour $c_i$. Otherwise, let $y_{k+1} \in \Gamma(x)$ be such that $\phi(x y_{k+1}) = c_k$, and let $c_{k+1}$ be a colour missing at $y_{k+1}$.
This process builds a list of distinct $y_i$ and $c_i$, so eventually it must terminate: it can only terminate if we find $c_{k+1}$ which has already appeared as an earlier $c_i$.
Wlog $c_1 = c_{k+1}$, because we can recolour $x y_j$ with colour $c_j$ for $1 \leq j \leq i-1$ and un-colour $x y_i$ itself.
Consider the subgraph of $G$ which is coloured only in colours $c_1, c$ (recalling that $c$ is the colour missing at $x$).
The maximum degree of this subgraph is $2$, so its components are paths and cycles; but $x, y_1, y_{k+1}$ all have degree $1$ in this subgraph and so must not lie in the same component.
If $x, y_1$ are disconnected in the subgraph, swap $c, c_1$ on the $c, c_1$-component of $y_1$, and let $\phi(x, y_1) = c$.
Otherwise, $x, y_{k+1}$ are disconnected in the subgraph, so swap $c$ and $c_1$ on the $c, c_1$-component of $y_{k+1}$, and recolour $x y_{k+1}$ by $c$, $x y_i$ by $c_i$ for each $i \in [1, k]$.
Best Answer
ORIGINAL (FLAWED) PROOF
Without loss of generality, let $G$ be connected. Let $e$ be a cut-edge with endpoints $u$ and $v$. Since $e$ is a cut-edge, its removal would separate $G$ into two components $H_1$ and $H_2$. This means that every path from a vertex in $H_1$ to a vertex in $H_2$ passes through $e$, and so every such path passes through both $u$ and $v$. Therefore, both $u$ and $v$ are cut-vertices.
ADDENDUM
As Joseph mentioned in the comments, a pendant edge is always a cut-edge, while a leaf cannot be a cut-vertex. Thus, the only way that both $u$ and $v$ fail to be cut-vertices is thus the case when $G$ is a single edge.
REVISED PROOF
Without loss of generality, let $G$ be connected. Let $e$ be a cut-edge with endpoints $u$ and $v$.
Note that if a vertex is a leaf, it cannot be a cut-vertex, since its removal does not increase the number of components of $G$. Thus, if $e$ is the only edge of $G$, then both $u$ and $v$ are leaves, and so $G$ possesses no cut-vertex.
Assume now that $G$ contains another edge $f$ distinct from $e$. Since $e$ is a cut-edge, its removal would separate $G$ into two components $H_u$ and $H_v$. This means that every path from a vertex in $H_u$ to a vertex in $H_u$ passes through $e$, and so every such path contains both $u$ and $v$. Now, one of $H_u$ or $H_v$ contains a vertex other than $u$ or $v$ (respectively), as $f$ belongs to one of these two components. Therefore, one of $u$ or $v$ is a cut-vertex. Furthermore, if neither $u$ nor $v$ is a leaf, then both $u$ and $v$ are cut-vertices.