We consider, in this dissertation, the question of determining if a graph has a property P, such as "G is triangle-free" or "G is 4-colorable". In particular, we consider for which properties P there exists a random algorithm with constant error probabilities that accept graphs that satisfy P and reject graphs that are epsilon-far from any graph that satisfies it. If, in addition, the algorithm has complexity independent of the size of the graph, the property is called testable. We will discuss the results of Alon, Fischer, Newman and Shapira that obtained a combinatorial characterization of testable graph properties, solving an open problem raised in 1996. This characterization informally says that a graph property P is testable if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions.