While all NP-hard optimization problems are identical in terms of exact solvability, they may differ wildly from the approximative point of view. If the goal is to obtain an answer that is “good enough”, some problems become much easier (such as KNAPSACK), while others (such as CLIQUE) remain extremely hard.

Graphs can be seen as a way to represent pairwise relationships between objects. With graphs, we have one object type and one relationship type. In one of the most common canonical applications or graph theory, social networking, we are trying to understand and represent social groups using graphs. In that case, our object is people, our pairwise relationship is friendship, and two people have a relationship between them if they are friends.

If you are like me, you did not particularly enjoy math in high school, so the idea of learning an entirely new type of math in university might be terrifying to you. I know this can be scary and overwhelming (it was for me!), so here are some things I learned when taking my first proof-based mathematics course. Hopefully you find this helpful.