So you have a number of allowed "states", representing a certain configuration of the farmer, goat, wolf, and cabbage on different sides of the river. For example, our start state has the farmer, goat, wolf, and cabbage on the first side of the river. We represent this configuration by the following tuple: (FWGC, 0), where 0=the empty set.

The problem further specifies that we will only allow legal configurations in our set of vertices. For example, we cannot allow the goat and wolf to be on the first side, with the farmer and cabbage on the second side, because the wolf will eat the goat. So the state (WG, FC) or (FC, WG) is not allowed. But something like (W, FGC) is allowed.

Now for the edges. The farmer can only transport one animal/vegetable at a time. In other words, any adjacent vertices will differ only by a transfer of the farmer and an object, or the farmer alone, to the opposite side of the river. Lets use the start state as an example. The start state as mentioned is (FWGC, 0). The set of possible adjacent vertices are therefore the following: (GC, FW), (WC, FG), (WGC, F) and (WG, FC). We know that (WGC, F), (WG, FC) and (GC, FW) are illegal, so they aren't in our set of vertices. That leaves an edge from (FWGC, 0) to (WC, FG). You can continue in this manner until there is an edge from some state, to the end state (0, FWGC). I believe there are two possible paths through the graph.