Library/Combinatorics/Graph Theory/Graph theory (other)

Graph theory (other)

Overview
Important

Beyond basic graphs, paths, cycles, and trees, graph theory includes many other important concepts such as connectivity, planarity, coloring, and special types of graphs. These ideas help us understand how graphs can be structured and analyzed in more complex ways.

Important properties

  • A graph is connected if there is a path between every pair of vertices.

  • A planar graph can be drawn on a plane without any edges crossing.

  • Graph coloring assigns colors to vertices so that no two adjacent vertices share the same color.

  • Special graphs include bipartite graphs (vertices can be split into two groups with no edges within a group), complete graphs (every pair of vertices is connected), and regular graphs (every vertex has the same degree).