I am trying to do the below problem:
Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$.
I read somewhere that this can't be done in polynomial time, and can only be done by brute force. Is this true?
It's an unsolved problem whether graph isomorphism can be decided in polynomial time. That's irrelevant here, because "polynomial time" is about large problems and asymptotics, and your problem is about a fixed pair of very small graphs.
It took me about a minute to find an isomorphism by trial. First, I looked at the big pentagon on the left, and labeled the vertices cyclically 1, 2, 3, 4, 5. Then I found a 5-cycle over on the right, and labeled the vertices there 1, 2, 3, 4, 5. Then I took the third neighbor of vertex 1 on the left and labeled it 6, and did the same on the right. And so on. Everything worked without a hitch, no backtracking needed.
What did you try?