# Pokemon and Graphs, Part 1

/Just recently I started replaying some of the older Pokemon games. It’s been a long time since I last played (around fifteen years or so), so I don’t know much at all about the strategy of the game. I usually pick my Pokemon based on how nice they look. I’m sure there are a million books and wiki articles out there about Pokemon strategy, but I haven’t read any of them. Let’s see what I can come up with on my own. I remember that there are different types (fire, water, etc) of Pokemon, and that they counter each other in a complicated rock-paper-scizzors thing. It seems that, ideally, you'd want a set of Pokemon that could counter any enemy type. I know I can only have six Pokemon active at a time. Given these conditions, what set of Pokemon should I choose?

Well, first I need to know what types of Pokemon there are and what they’re strong against. My vague memories tell me there’s at least, like, six kinds of them. After poking around on the internet, I found a handy chart that shows all the attack modifiers. This would be really helpful if all I wanted was to to check is one or two relationships, but it won't answer my question very well.

To do that, I need a graph.

A graph is a mathematical object that consists of a set of vertices and a set of edges, each of which connects a pair of vertices. Edges can be directional (like arrows). In multigraphs, a pair of vertices can have more than one edge between them, and edges can loop. Graphs are used in all sorts of math problems, and today, they are going to help me pick a set of Pokemon.

Let’s start arranging the chart into a graph. I’m going to make each type a vertex (so I’ll have 18 vertices) and I’ll make those attack modifiers into edges. Attacks are one-way, so I'll use arrows for edges, and Pokemon sometimes fight their own type, so some edges will be loops. Therefore, this will be a directed multigraph.

There’s one more thing. A graph with all possible edges included is called a complete graph. If I draw in every single attack relationship, I would have 324 edges! The diagram would be unreadable. Since I just care about strengths, I'll only draw the x2 modifiers.

Copyright 2014 Lauren Ellenberg. Pokemon is copyright Pokemon Corporation/Nintendo.

So now I have my graph. What I want from this graph is a dominating set. A dominating set is a set of vertices such that every vertex in the graph is in the set or adjacent to it. I’d like a minimal set, meaning that I don’t have extra Pokemon I could go without.

There are a couple of wrinkles that keep this problem from being strictly “find a dominating set.” First, we can only have 6 Pokemon active at a time, so I’m really hoping for a dominating set of six vertices or less. Second, Pokemon are rarely strong against themselves, so not only do I need a dominating set, but also each of the vertices in the dominating set must be adjacent to another vertex in the set.

Vertices in dominating set colored black. Copyright 2014 Lauren Ellenberg. Pokemon is copyright Pokemon Corporation/Nintendo.

I tried to find a set of six points, but I could only find sets of seven or greater. If you’d like to try it yourself, the logic chain that got me to this solution is at the bottom of the post. Now that I’ve gotten myself a dominating set, there are two things going for me. First, there are a lot of choices of Pokemon for each type. One of them is bound to be not ugly. Second, Pokemon can be dual-type, meaning that the number of Pokemon I need is smaller than the number of vertices in the dominating set. This means that for any appropriate dominating set, there’s a great variety of Pokemon that can fill in. That should be enough for anyone’s choice of strategy or aesthetic value.

#### Notes

Here’s how I got my solution: 1) Electric can only be dominated by ground. Pick ground. 2) Normal is only dominated by Fighting. Pick fighting. 3) Ghost is dominated only by dark or itself. Dark dominates the same types as ghost. Choice is irrelevant; pick dark. 4) Dragon needs ice or fairy; fairy only adds flying, but ice adds flying and more. Pick ice. 5) Water needs grass or electric; neither adds anything, so choice is irrelevant. Pick grass. 6) Fighting is dominated by psychic or flying; poison adds nothing, choose flying. 7) Only remaining type is fairy, dominated by poison or steel. Choice is irrelevant, pick poison.

Choices: ground, fighting, dark, ice, grass, flying, poison. There are some alternate equivalent solutions. You can pick either ghost or dark, either grass or electric, and either poison or steel. That means there are 8 possible solutions with 7 types. Interestingly, using this method, you would never pick normal, dragon, fire, bug, psychic, rock, fairy, or water. Regardless, you can use this diagram to put together whatever combos you want, based on your current set of Pokemon.