Planar Graphs and Graph Coloring in Discrete Mathematics

Explore planar graphs and graph coloring in discrete mathematics. This guide defines planar graphs, discusses their properties (regions, Euler's formula), and introduces graph coloring, including the Four Color Theorem, providing examples and illustrations.

Planar Graphs and Graph Coloring in Discrete Mathematics

Planar Graphs

A planar graph is a graph that can be drawn on a plane (a flat surface) without any edges crossing. Think of drawing the graph on a piece of paper without any lines overlapping.

Example: A Planar Graph

(An illustrative planar graph would be included here.)

Regions in a Planar Graph

A planar graph divides the plane into regions. One of these regions is unbounded (the infinite region or exterior region); the others are bounded (finite regions or interior regions).

Example: Identifying Regions

(An illustrative planar graph would be included here, clearly showing the regions. The number of finite regions and infinite regions would be identified.)

Properties of Planar Graphs

  • Property 1: If a connected planar graph has 'e' edges and 'r' regions, then r ≤ e.
  • Property 2 (Euler's Formula): For a connected planar graph with 'v' vertices, 'e' edges, and 'r' regions: v - e + r = 2.
  • Property 3: For a connected planar graph with 'v' vertices and 'e' edges: 3v - e ≥ 6.
  • Complete Graphs: Kn is planar if and only if n < 5.
  • Complete Bipartite Graphs: Km,n is planar if and only if m ≤ 2 or n ≤ 2.

Example: Proving K₄ is Planar

(The proof showing that the complete graph K₄ is planar by demonstrating that it satisfies the inequality 3v - e ≥ 6 is given in the original text and should be included here.)

Non-Planar Graphs

A non-planar graph cannot be drawn on a plane without edges crossing.

Example: Non-Planar Graphs

(Illustrative examples of non-planar graphs would be included here.)

Properties of Non-Planar Graphs

A graph is non-planar if and only if it contains a subgraph homeomorphic to K₅ or K₃,₃ (Kuratowski's Theorem).

Examples: Showing Non-Planarity

Example 1: K₅ is Non-Planar

(The proof demonstrating that K₅ is non-planar by showing that it does not satisfy the inequality 3v - e ≥ 6 is given in the original text and should be included here.)

Example 2: Showing Non-Planarity Using Subgraphs

(This example, demonstrating non-planarity by finding subgraphs homeomorphic to K₅ or K₃,₃, is given in the original text and should be included here.)

Graph Coloring

Graph coloring involves assigning colors to vertices such that no two adjacent vertices share the same color. A graph is M-colorable if it can be colored using at most M colors.

Proper Coloring

A proper coloring is one where no two adjacent vertices have the same color.

Chromatic Number (χ(G))

The chromatic number χ(G) of a graph G is the minimum number of colors needed for a proper coloring.

(An example showing a proper coloring of a graph and its chromatic number would be included here.)

Applications of Graph Coloring

  • Register allocation in compilers
  • Map coloring
  • Bipartite graph checking
  • Mobile radio frequency assignment
  • Timetable scheduling

Handshaking Theorem

The Handshaking Theorem states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges: Σv∈V deg(v) = 2|E|.

(A proof of the Handshaking Theorem is given in the original text and should be included here.)

Conclusion

Planar graphs and graph coloring are important areas within graph theory, with wide-ranging applications in various fields.