Prove that cycle of length 3 exists in a 4-regular connected graph that has $3n+2, n \in N$ vertices

Question

How to approach proving that? For $n=1$ the number of vertices is 5, which is a full graph, which obviously has a cycle of length 3. Doing the proof by mathematical induction makes no sense to me here.

Sum of degrees of all the vertices is $4(3n+2), n \in N$, so the number of edges is $4(3n+2)=2|E|, n \in N$, so the number of edges is $|E| = 2(3n+2)$

Maybe proof by contradiction could be used? But how? I am stuck.

Edit: The graph is connected

Answer 1

The most general example I can come up with is the Cartesian product of two connected 2-regular bipartite graphs, i.e. even cycles. Let $k,\ell > 1$ be positive integers; then $C_{2k} \square C_{2\ell}$ satisfies the desired properties of a counterexample:

1. It's connected since each cycle is connected
2. It's 4-regular since each cycle is 2-regular (the degrees add)
3. It's bipartite since each cycle is bipartite, so it does not contain a triangle
4. It has $2k \cdot 2\ell$ vertices, which for particular values of $k$ and $\ell$ takes on the desired values. For instance, $k=2$ and $\ell=4$ gives $32 = 3\cdot 10 + 2$ vertices.

If you aren't familiar with the Cartesian product, an equivalent formation of this graph is as follows: the vertex set is $V = \{1,\dots,2k\} \times \{1,\dots,2\ell\}$ where $(i,j),(i',j') \in V$ are adjacent if and only if ($i=i'$ and $j-j' = \pm 1 \pmod{2\ell}$) or ($j=j'$ and $i-i' = 1 \pmod{2k}$.