**First solution:** We will prove this using an induction on \(k\). Let \(P(k)\) be the following statement:
\[P(k)\equiv ^{\prime\prime} \mbox{There exists a graph that is triangle-free and has }C_5\mbox{ as a subgraph.}^{\prime\prime}\]
The statement \(P(2)\) is true since the graph \(C_5\) satisfies the conditions.

Assume that \(k\geq 3\) and that the statement \(P(k-1)\) is true. Consider the graph \(G_{k-1}=(V,E)\) such that each vertex has degree \(k-1\), there are no subgraphs \(C_3\) and there is a subgraph \(C_5\). Let us denote by \(A_1\), \(A_2\), \(\dots\), \(A_m\) the vertices of the graph \(G\).

Consider a graph \(G^{\prime}_{k-1}=\left(V^{\prime},E^{\prime}\right)\) whose vertices are \(A_1^{\prime}\), \(A_2^{\prime}\), \(\dots\), \(A_m^{\prime}\) such that \(\left(A_i^{\prime},A_j^{\prime}\right)\in E^{\prime}\) if and only if \(\left(A_i,A_j\right)\in E\). In other words, the graph \(G^{\prime}_{k-1}\) is isomorphic to \(G_{k-1}\) with an isomorphism \(\varphi\) that maps \(A_i\) to \(A_i^{\prime}\) for each \(i\in\{1,2,\dots, m\}\).

Let us construct the graph \(G_{k+1}=\left(V_{k+1},E_{k+1}\right)\) with \(V_{k+1}=V\cup V^{\prime}\) and \(E_{k+1}\) is the union of all edges from \(E\) and \(E^{\prime}\), together with edges between \(A_i\) and \(A_i^{\prime}\) for every \(i\in\{1,2,\dots, m\}\).

The graph \(G_{k+1}\) does not contain cycles of length \( 3\) because such cycles would have to be fully inside of one of the subgraphs isomorphic to \(G_{k-1}\). It does contain cycles of length \(5\) because it contains \(G_{k-1}\) as a subgraph.

**Second solution:** For \(k=2\), an example is \(C_5\). Assume that \(k\geq 3\).
Let us consider the graph \(G_1=\left(V,E\right)\) whose set of vertices \(V\) consists of \(2^k\) sequences \(\left(a_1, a_2, \dots, a_k\right)\) of length \(k\) whose terms are from the set \(\{0,1\}\). Two vertices with labels \(\left(a_1, a_2, \dots, a_k\right)\) and \(\left(b_1, b_2, \dots, b_k\right)\) are connected with an edge if and only if the sequences differ in exactly one component. Since each vertex is labeled by a sequence with \(k\) terms, there are exactly \(k\) other sequences each of which differs in exactly one coordinate. Thus the degree of each vertex is \(k\).

We will now construct a graph \(G=\left(V,F\right)\) by using the same set of vertices \(V\) but by modifying the set of edges \(E\) and creating a new set \(F\). Let us denote by \(e_1\) the edge between \((0,0,0,\dots, 0)\) and \((1,0,0,\dots, 0)\) and by \(e_2\) the edge between \((0,1,0,\dots, 0)\) and \((1,1,0,\dots, 0)\). Let us denote by \(\overrightarrow z\) the sequence of \(k-3\) zeroes. With this helpful notation we can write \(e_1\) as the edge between
\(\left(0,0,0,\overrightarrow z\right)\) and \(\left(1,0,0,\overrightarrow z\right)\). Similarly, \(e_2\) is the edge between \(\left(0,1,0,\overrightarrow z\right)\) and \(\left(1,1,0,\overrightarrow z\right)\). We will remove the edges \(e_1\) and \(e_2\) from the set \(E\), and add the following two edges:
\begin{eqnarray*}
f_1 &=& \mbox{edge between }\left(0,0,0,\overrightarrow z\right)\mbox{ and }\left((1,1,0,\overrightarrow z\right)\newline
f_2 &=& \mbox{edge between }\left((1,0,0,\overrightarrow z\right)\mbox{ and }\left((0,1,0,\overrightarrow z\right).
\end{eqnarray*}
Thus the set \(F\) is created in the following way: \[F=\left(E\setminus\left\{e_1,e_2\right\}\right)\cup \left\{f_1,f_2\right\}.\]
Each vertex of the graph \((V,F)\) has degree \(k\). However, the graph \((V,F)\) is not bipartite because we will show that it has the following cycle of length \(5\):
\begin{eqnarray*}
\left(0,0,0,\overrightarrow z\right), \left(1,1,0,\overrightarrow z\right), \left(1,1,1,\overrightarrow z\right), \left(1,0,1,\overrightarrow z\right),
\left(0,0,1,\overrightarrow z\right).
\end{eqnarray*}