Graph Theory : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

A graph is a collection of dots which are connected (and sometimes not connected) by lines in some pattern. These lines can be either straight or curved. Graph theory is the study of such spatial structures. Undirected and directed graphs are discussed in this chapter. Several special graphs are also defined. In addition, different graph operations, representations, and transformations are also outlined. Planar graphs, and some useful observations about graphs, and spanning trees are also discussed. The K-core, K-crust, and K-shell of a graph are introduced. Basics of matroid theory, and graph spectrum are also studied. Some results in this chapter are based upon the theory of matrices and determinants. This later subject is discussed in a different chapter.