Chapter 1 pointed out that NP-complete problems are a “stumbling block” hindering the development of today’s technology. Due to the natural advantage of DNA computing’s parallelism in solving NP-complete problems, research on DNA computing over the past decades has mainly focused on solving NP-complete problems. Considering that many NP-complete problems are graph theory problems, this chapter first introduces some basic knowledge in graph theory; then, it gradually reveals the true nature of NP-complete problems and introduces some related theories of NP-complete problems, especially computational complexity theory.