This is the fourth part of the graph theory notes. We take a look at Trees. The book followed throughout is: Graph Theory with Applications by Bondy J.A., Murty U.S.R.. Please refer to the book for examples as well as visual graph drawings. Trees Before introducing trees, here are some essential terminologies: Let $G$ be a graph and its edges are $e_1,e_2,e_3,e_4,\ldots,e_m$ If edge $e_i = (v_{i-1},v_i)$ for $i = 1,2,3, \ldots, m$ exists and $v_{i-1}$ is adjacent to $v_i$ then we call the sequence a chain from $v_0$ and $v_m$.

This is the third part of the graph theory notes. We take a look at $k$-partite graphs and Turán’s Theorem. We omit the Tactics section since most problems can be handled by tactics mentioned earlier combined with the powerful results mentioned below. However, it might be worthwhile to see the connection of Inequalities (like - AM-GM, Cauchy-Schwartz etc) to problems related with finding bounds of edges. The book followed throughout is: Graph Theory with Applications by Bondy J.

This is the second part of the graph theory notes. We take a look at Degree of a Vertex and the so-called Hand-Shaking Lemma in this post. The book followed throughout is: Graph Theory with Applications by Bondy J.A., Murty U.S.R.. Please refer to the book for examples as well as visual graph drawings. Degree of a Vertex The degree of a vertex $v$ in a graph $G$, denoted by $d_G(v)$ (or simply, $d(v)$ if the context of graph is clear), is the number of edges incident to $v$ of $G$.

This is a series of my notes on graph theory and usage in Scholarship Problems. We look at what a graph is today and present some terminologies. We also present some basic tactics to solve elementary problems. Following the tradition of this blog, we do not present any illustrations on using the tactics as it limits the readers to thinking about the problems only through a specific approach whereas in an exam environment multiple approaches and various combination of techniques is necessary.