After you arrive in Rustboro City and explore the sites, you can go to the Rustboro Gym and challenge the Rock-type pokémon of the trainers and Roxanne.

Prepare

The pokémon that you will face in this gym are Rock-type pokémon. Rock-types are weak to Water, Grass, Steel, Ground, and Fighting moves. But Rock-type moves are strong against Flying-type, Bug-type, Fire-type, and Ice-type pokémon, so don't bring any of those with you to this gym.

Some of the pokémon that you have encountered so far that would work well in this gym are Lotad, Seedot, and Shroomish. In addition, if you chose Treecko or Mudkip as your starter, it will work well against Rock-type pokémon.

Battle the Trainers, or Not

In this gym, you can walk behind things to avoid battling the trainers along the path.

But if you decide to battle the trainers anyway, you will encounter Youngster Josh, who has two Geodudes, then Youngster Tommy, who has a Geodude, then Schoolkid Georgia, who has a Geodude.

Finally, go up the stairs in the back of the room and talk to Roxanne to battle her.

Roxanne

Roxanne has a Geodude and Nosepass. Roxanne has a Potion with her that she may use to heal her pokémon during the battle. In addition, her Geodude has the Ability Sturdy, which makes it survive with 1HP if it is at full health and is hit with an attack that would otherwise make it faint.

After you Win

After you defeat Roxanne, she gives you the Stone Badge (which has a little pin on the back, which is awesome) and also gives you TM39 Rock Tomb. The move Rock Tomb is a Rock-type move that deals damage and also reduces the opponent's speed.

When you go outside, you see a Team Magma/Aqua Grunt run away, and a Devon Researcher running after. Go up and talk to the Researcher. He is the same one you helped in the Petalburg Woods. The Grunt stole the Devon Parts, and the researcher asks you to get them back. The Grunt went to Route 116.

Cut Some Trees

But before you go there, you might want to teach Cut to one of your pokémon. Treecko and Torchic can learn it, as well as Zigzagoon and Slakoth. Since Cut is a Normal-type move, it might be better to teach it to Zigzagoon or Slakoth because they are Normal-type, so they will do more damage with Cut in battle than other types of pokémon.

There is a tree that you can cut in the north part of Route 104 in the southeast corner. Beyond that tree, you find a Revive.

There is also a tree that you can cut in the Petalburg Woods in the northeast corner. Beyond that tree, there is some grass, and in a small gap above that grass, you can find a hidden Tiny Mushroom.

To the northeast, talk to the girl to get a Miracle Seed. If you give it to a pokémon, its Grass-type moves will be stronger.

Northeast of that girl, there is a Great Ball.

In the northeast corner of Petalburg Woods, there is a moss-covered rock.

South from there, you can find an X Attack.

Continue On

Now that you have explored new areas made accessible with Cut, you should go to Route 116 to look for the Grunt who stole the Devon Parts.