In this thesis, we will focus on two of Karp's original NP-complete problems, graph coloring and max cut, both of which have established semidefinite programming relaxations. We introduce the use of semidefinite programming complementary slackness conditions to understand when an optimal solution to one of these SDP relaxations can be guaranteed to take the form of an optimal solution to the original problem. First, we consider the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is a $k$-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if a graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. We then modify the semidefinite program to have an objective function with costs, and explore when we can create an objective function such that the optimal dual solution has sufficiently high rank. We show that it is always possible to construct such an objective function given the graph coloring. The construction of the objective function gives rise to heuristics for 4-coloring planar graphs which we also present. We enumerated all maximal planar graphs with an induced $K_4$ of up to 14 vertices; the heuristics successfully found a 4-coloring for 99.75% of them. Then we switch settings to max cut. We investigate when the rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank $n -1$. We show in the case of connected bipartite graphs that they have sufficiently high dual rank. Analogously to graph coloring, we also show that if the max cut of a graph is not unique, then there cannot exist an optimal dual solution of sufficiently high rank. We conclude with a theorem and corresponding conjecture for general graphs. Finally, we switch to an experimental perspective and evaluate the performance of several max cut approximation algorithms. In particular, we compare the results of the Goemans and Williamson algorithm using semidefinite programming with Trevisan's algorithm using spectral partitioning. The former algorithm has a known .878 approximation guarantee whereas the latter has a .614 approximation guarantee. We investigate whether this gap in approximation guarantees is evident in practice or whether the spectral algorithm performs as well as the SDP. We also compare the performances to the standard greedy max cut algorithm which has a .5 approximation guarantee, two additional spectral algorithms, and a heuristic from Burer, Monteiro, and Zhang. The algorithms are tested on Erd\H{o}s-Renyi random graphs, complete graphs from TSPLIB, and real-world graphs from the Network Repository. We find, unsurprisingly, that the spectral algorithms provide a significant speed advantage over the SDP. In our experiments, the spectral algorithms and BMZ heuristic return cuts with values which are competitive with those of the SDP.