One property of graphs quickly becomes apparent to the budding graph theorist: there are many ways to render graphs. On the page, the same graph may be drawn different ways, the vertices placed in different positions. How then can we know whether two renderings on a page describe the same graph?
First, let's define what we mean by "the same" or isomorphic.
Two graphs are isomorphic if there is a one-to one mapping between their vertices such that there is an edge between two vertices of one graph iff there is an edge between the corresponding vertices in the corresponding graph.
Graph isomorphism is an equivalence relation, and so if G and H are isomorphic, the relation is written as G = H.
Thus, to determine whether two graphs are the same, the resourceful mathematician only needs to find this one-to-one mapping.
The problem of Graph Isomorphism, testing whether two graphs are the same, is an interesting problem in the theory of algorithms. Graph Isomorphism has not been shown to be solvable in polynomial time, but neither has it been shown to be NP-complete.
In fact, many believe that this problem belongs to a class of problems that are in neither P nor NP-complete; though of course it has not yet been proven, since proving this implies P != NP