Given a graph, we are often interested in deciding if it satisfies a certain property. Some examples of graph properties include connectivity, bipartiteness, and planarity.