Answer to Question #102505 in Discrete Mathematics for Roshanthi

Question

1. Construct a proof for the five color theorem for every planar graph.
2. Discuss how efficiently Graph Theory can be used in a route planning project for a vacation trip from Colombo to Trincomalee by considering most of the practical situations (such as mileage of the vehicle, etc.) as much as you can. Essentially consider the two fold,
- Routes with the shortest distance (Quick route travelling by own vehicle)
- Route with the lowest cost

Answer 1

1.Theorem: Every planar graph with n vertices can be colored using at most 5 colors.

PROOF:

Using the method of proof by induction, we induct on n, the number of vertices in a planar graph G.

Base case, P(n≤5): Since there exist ≤5 nodes in G, the graph can be colored using 5 colors.

Inductive step, P(n+1): Assuming P(n) is true, that is, every planar graph with n vertices, we need to show P(n) is true.

We know every planar graph has one vertex with deg(v)≤5 (Lemma). Let this vertex be called v in our graph G. Remove v and for the remaining sub-graph G′ we can assume P(n).

If deg(v)≤4, we can color all vertices adjacent to v using 4 colors and use color 5 to color v itself to reach a valid coloring.

If deg(v)=5, we assume that all vertices adjacent to v are colored in different colors.

Hence Proved.

2.Graph theory can be applied in a route planning project for a vacation trip from Colombo to Trincomalee in the following way :

It is done by first searching a graph, starting at one point, and exploring adjacent nodes from there until the destination node is reached. Generally, the goal of this route panning is of course to obtain the shortest route to the destination.

The main objective is to reduce path-request blocking and increase overall utilization. The weighted graphs, along with generalizations of algorithms can be used for finding optimal routes, that is the routes with shortest distance as well as those with the lowest cost.

Weights on the graph's edges are assigned according to real life parameters, which means actual situation on the road such as weather conditions, and road capacity at the specified time. The two key issues that need to be addressed in this application of Graph Theory are to determine the addition of two edges and to compare the distance between two different paths with their edge lengths.