The Graph below represents a map of Manhattan and four surrounding land masses with bridges and tunnels connecting to Manhattan.
Key
NJ- New Jersey LT-Lincoln Tunnel
M-Manhattan BBT- Brooklyn Battery tunnel
BR- Brooklyn BB- Brooklyn Bridge
B- Bronx WB-Williamsburgh Bridge
Q-Queens QMT-Queens Midtown Tunnel
QB-Queensbrough Bridge WAB-Willis Avenue Bridge
TB-Triborough Bridge TAB- Third Avenue Bridge
GW- George Washington Bridge HT-Holland Tunnel
- The degree of a vertex implies the number of edges joined to that vertex.
The degrees of vertices in the Graph above are as follows are:
- Vertex M is of degree 13
- Vertex B is of degree 4
- Vertex Br is of degree 4
- Vertex Q is of degree 4
- Vertex NJ is of degree 3
- The Graph an Euler Path and no Euler Circuit. This is because it has exactly two odd vertices, vertex M and NJ. According to the Euler theory, such Graph could have an Euler Path but no Euler Circuit. An Euler Path passes through each edge of the Graph exactly one time while an Euler circuit passes through each edge of the Graph exactly one time, beginning and ending at the same vertex. The following illustrates an Euler Path in the Graph above. This Path begins with one of the odd vertices, and ends with the other.
An Euler Path: HT,LT,GW,TAB,WAB,TB3,TB2,TB1,QB,QMT,WB,MB,BB,BBT
- There is no Bridge in the Graph. According to the Graph Theory, a bridge could only exist when there is an edge of which if removed, could lead to a disconnected graph. The Graph above remains a connected graph, even if any edge is removed. Therefore, since there exists no edged, such that if removed, could lead to a disconnected Graph, a bridge doesn’t exist in the Graph above. Furthermore, this indicates that all vertices are connected to multiple edges, and in this case, they overlap.
The Graph below illustrates the ceremony scheduling, by connecting two vertices with an edge, if the Ceremony cannot be scheduled in the same day in the two locations represented by the vertices.
The assumption for this Graph is that a ceremony in Brooklyn cannot be scheduled in the same day with the ceremony in Bronx, which is the second case in our assumptions.
- This Graph is planar. Since the Graph does not have any edges intersecting but all edges meet at a given vertex, then, according to graph theory the Graph is embeddable in a plane and hence planar. Where m is the number of edges, n is the number of vertices and f is the number of faces, the following properties for planar graphs is fulfilled.
n=5, m=5 and f=2
Condition 1 (Euler): n−m+ f = 2
Condition 2: m ≤ 3n−6
Condition 3: 2m ≤ 6n
- According to Graph Theory, any Graph could require ∆G+1 coloring. Since ∆G=n-1, where n is the number of vertices of the Graph, then the number of vertices in this Graph is 5, hence it is 5-colourable.
- The degrees of the Graph above are as follows:
- Vertex M is of degree 4
- Vertex B is of degree 2
- Vertex Br is of degree 1
- Vertex Q is of degree 2
- Vertex NJ is of degree 1.
- Using the Greed Algorithm, we can obtain the optimum number of coloring the vertices.
Let the set of our colors be {1,2,3,4,5} , where 1 is red, 2 is green, 3 is blue, 4 is yellow, and 5 is violet.
Step 1: We take vertex Q to be the uncolored vertex.
Step 2: Then, we remove Q and all its adjacent edges and color the remaining graph recursively.
Step 3: Finally, we put Q and its adjacent edges back and assign it with a color that is not contained by any of its neighbors.
- The maximum number of colors used to color the Graph three days. This indicates that the maximum number of days required for holding ceremonies sufficiently in New Jersey, Manhattan, Brooklyn, Bronx, and Queens.
- If the first event is to be held on Monday, then the following shall be the schedule of all ceremonies.
Monday: Ceremonies shall be held in Brooklyn and The Bronx.
Tuesday: A ceremony shall be held in Manhattan.
Wednesday: Ceremonies shall be held in Queens and New Jersey.
Application of graph coloring in the real life
Graph coloring is a very important tool in making optimal decisions. In life I could apply the graph coloring in research especially during field work. The objective could be to reduce the cost associated with each particular aspect for data collection. For instance, in an exercise of collecting data from stratified samples in a population of study, there may be several paths of travelling with various associated costs and a limited number of research personnel. Graph coloring could be used in this case to reduce the costs incurred by determining the minimum number of days required to complete the exercise.
