Answering questions about graphs has many uses in computer science. Particularly important is finding ways to answer questions about graphs in a way that scales well with the size of the graph. Some questions can be answered in time that is bounded by a polynomial in the number of vertices in the graph; those problems belong to class P. Other questions are decision problems (with a yes or no answer) where if the answer is yes, there is a solution we can verify in polynomial time; those problems are in class NP. The class of NP-complete problems consists of decision problems to which any decision problem in NP can be reduced in polynomial time. This talk exhibits how several important graph theory problems can be shown to be NP-complete through clever polynomial reductions, starting from the NP-complete problem of finding an assignment of Boolean variables that makes a Boolean formula true (the satisfiability problem). This talk also includes a brief overview of elementary graph theory.