9.1 Complete Graphs

In this section, you learned how graphs are used to model relationships between objects using vertices and edges. You studied basic graph terminology, including adjacency, incidence, paths, loops, parallel edges, and simple graphs. You then focused on complete graphs, denoted [latex]K_{n}[/latex], in which every pair of distinct vertices is connected by a unique edge. You derived and applied the formula [latex]\frac{n(n-1)}{2}[/latex] to compute the number of edges in a complete graph and examined key properties such as symmetry, density, and uniform vertex degree. The concept of bipartite graphs and complete bipartite graphs [latex]K_{m, n}[/latex]  was also introduced, highlighting their role in modelling systems with two distinct classes of entities.

9.2 Connected Graphs

This section examined what it means for a graph to be connected, emphasizing the role of paths in determining reachability between vertices. You learned that disconnected graphs decompose into components, each of which is a maximal connected subgraph. Additional path concepts were introduced, including simple paths, cycles, and simple cycles. A major focus of this section was on Euler cycles and Euler trails, which are paths or cycles that traverse every edge exactly once. You learned precise degree‑based conditions for when Euler cycles and Euler trails exist, supported by Theorems 9.1 and 9.3. You also studied the Total Degree Theorem (Theorem 9.2), which states that the sum of the vertex degrees equals twice the number of edges, and used it to verify the graph's correctness.

9.3 Directed Graphs

In this final section, you extended graph concepts to directed graphs (digraphs), where edges represent one‑way relationships. You learned how to interpret directed edges and compute the indegree and outdegree of vertices to analyze flow and dependencies. Conditions for the existence of a directed Euler cycle were established, requiring the underlying undirected graph to be connected and every vertex to have equal indegree and outdegree. The section also introduced directed acyclic graphs (DAGs), which contain no cycles and are essential for modelling task dependencies and workflows. You studied properties of DAGs, including the guarantee that at least one vertex has outdegree zero, enabling topological ordering.