Planar Graphs in Discrete Mathematics: Understanding Embeddings on a Plane
Learn about planar graphs, graphs that can be drawn on a plane without any edges crossing. This guide defines planar graphs, discusses their properties (regions, Euler's formula), and provides examples illustrating planar and non-planar graphs.
Planar Graphs in Discrete Mathematics
What is a Planar Graph?
A planar graph is a graph that can be drawn on a plane (a flat surface) in such a way that no two edges cross each other. Imagine you can draw the graph on a piece of paper without any of the lines overlapping.
Example: A Planar Graph
(An illustrative planar graph would be shown here.)
Regions of a Planar Graph
When a planar graph is drawn on a plane without edges crossing, it divides the plane into several regions. One of these regions is unbounded (the exterior region); the others are bounded (interior regions).
Degree of a Region
The degree of a region is the number of edges that border that region. The degree of the exterior region is the number of edges forming its boundary.
Example: Regions and Their Degrees
(An illustrative planar graph would be included here, clearly showing the regions and labeling their degrees.)
Chromatic Number of Planar Graphs
The chromatic number of a graph is the minimum number of colors needed to color the vertices such that no two adjacent vertices (vertices connected by an edge) share the same color. The Four Color Theorem states that the chromatic number of any planar graph is at most 4.
Properties of Planar Graphs
- Property 1 (Sum of Vertex Degrees): The sum of the degrees of all vertices is twice the number of edges: Σv∈V deg(v) = 2|E|.
- Property 2 (Sum of Region Degrees): The sum of the degrees of all regions is twice the number of edges: Σr∈R deg(r) = 2|E|.
- Euler's Formula: For a connected planar graph with v vertices, e edges, and r regions: r = e - v + 2. This formula holds for any planar representation of the graph.
- Euler's Formula (Disconnected Graph): For a planar graph with k connected components, v vertices, e edges, and r regions: r = e - v + k + 1
Examples: Applying Euler's Formula
Example 1: Finding the Number of Regions
(An example where the number of vertices and edges are given, and Euler's formula is used to calculate the number of regions would be included here.)
Example 2: Finding the Number of Regions (Disconnected Graph)
(An example of a disconnected planar graph would be given here, where the number of vertices, edges, and components are given. Euler's formula for disconnected graphs would be used to find the number of regions.)
Example 3: Finding the Number of Regions Given Vertex Degree
(An example where the number of vertices and the degree of each vertex are given. The number of edges would be calculated using the handshaking lemma, and Euler's formula would then be used to find the number of regions.)
Example 4: Finding the Number of Vertices Given Region Degree
(An example where the number of regions and the degree of each region are given. The number of edges would be calculated, and Euler's formula would then be used to find the number of vertices.)
Example 5: Finding Region Degree
(An example where the number of edges, vertices, and regions are given. Euler's formula would be used to find the degree of each region assuming all regions have the same degree.)
Example 6: Maximum Number of Regions for a Given Number of Edges
(An example demonstrating how to calculate the maximum possible number of regions for a given number of edges using the fact that the minimum degree of a region in a simple planar graph is 3 would be shown here.)
Example 7: Maximum Number of Edges for a Given Number of Regions
(An example demonstrating how to calculate the maximum possible number of edges for a given number of regions using the fact that the minimum degree of a region in a simple planar graph is 3 would be shown here.)
Conclusion
Planar graphs are an important class of graphs with unique properties and applications. Euler's formula provides a powerful tool for analyzing the relationship between vertices, edges, and regions in planar graphs.
Maximum Edges and Regions in Planar Graphs
Maximum Number of Regions
Given a simple planar graph (a planar graph with no loops or multiple edges) with 'e' edges, we can determine the maximum number of regions it can have. In a simple planar graph, the minimum degree of any region is 3 (a region must be bounded by at least three edges).
Using the property that the sum of the degrees of all regions is twice the number of edges (Σr∈R deg(r) = 2|E|), and knowing that the degree of each region is at least 3, we can derive the inequality:
3|R| ≤ 2|E|
Where |R| is the number of regions and |E| is the number of edges. This inequality gives us an upper bound on the number of regions.
Example: Maximum Regions
What is the maximum number of regions possible in a simple planar graph with 10 edges?
Solution: 3|R| ≤ 2 * 10 => |R| ≤ 20/3 ≈ 6.67. Since the number of regions must be a whole number, the maximum number of regions is 6.
Maximum Number of Edges
Similarly, given a simple planar graph with 'r' regions, we can find the maximum number of edges. Again, using the fact that the minimum degree of a region is 3, we get:
3r ≤ 2e
Where 'e' is the number of edges. This inequality provides an upper bound on the number of edges.
Example: Maximum Edges
What is the maximum number of edges possible in a simple planar graph with 15 regions?
Solution: 3 * 15 ≤ 2|E| => |E| ≥ 45/2 = 22.5. Since the number of edges must be a whole number, the minimum number of edges is 23.
Conclusion
These calculations demonstrate how the minimum degree of a region (3, for simple planar graphs) can be used to find upper bounds on the number of regions and edges in a simple planar graph.