Creation of a Graph
In order to better expand upon graph properties and vertex coloring, we created the graph Dn. We defined the graph Dn to be a graph in which a cycle graph Cn is contained as a subgraph in which every vertex along the cycle is connected to P2.
From observations of these particular graphs, we can take note that the number of vertices is equivalent to the number of edges. Every vertex on the Cn graph will have an extended vertex from the P2 graph. A cycle subgraph has always either a chromatic number of two or three. A path subgraph extending from the cycle path will have a chromatic number of two always. Based on the relationship between the cycle and path graphs within the Dn graph, we can propose that any graph Dn containing a C2n subgraph has the chromatic coloring X(Dn) = 2. Similarly, any graph Dn containing a C2n+1 subgraph has the chromatic coloring X(Dn) = 3.
Proof of Coloring for an Even- Cycle Graph
We can first take into consideration the vertex colorings of a C2n and Cn +1 graph. A C2n graph has a chromatic number of two. We can prove this by way of induction. We can think of induction as a set of dominoes. It is simply the process of stating that if one property can be proved in a graph, (if one domino can fall over) then the rest of this graph family follows the same logic (all the dominoes fall over).
A C4 graph has the chromatic coloring X(C4) = 2.
We now assume that C2n has the chromatic coloring X(C2n) = 2. We will use this assumption to show that C2n + 2 (the next cyclic graph with even vertices) has the chromatic coloring X(C2n + 2) = 2.
We start with our Cn graph and add two vertices along the cycle and color them accordingly. Without generality, since the nth cyclic graph is assumed to be 2 colorable, then we know whenever we place these two vertices we know that they are either adjacent to a red or blue vertex. Therefore, we know that we can color the vertices either red or blue depending on what they are adjacent to
Proof of Coloring for an Odd- Cycle Graph
Similarly, we can prove that a C2n + 1 graph has the chromatic coloring X(C2n+1) = 3 by means of induction.
A C3 graph has a chromatic number of X(C3) = 3.
Now we can assume that Cn has the chromatic number X(C2n+1) = 3. We can use this assumption to show that C2n+1 has the chromatic number X(C2n+3) = 3.
We start with C(2n+1), which has been assumed to have X(C2n+1) = 3. Without generality, since the nth cyclic graph is assumed to be 3 colorable, then we know whenever we place these two vertices we know that they are either adjacent to a red or green vertex. Therefore, we know that we can color the vertices either red, green, or blue depending on what they are adjacent to.
Coloring a Dn Graph
Looking back at our Dn graph, we can apply the logic taken from these proofs to explain that any Dn can be colored with either two or three colors. We’ve already established that this graph contains either a C2n + 1 or C2n subgraph. In addition, we’ve also already defined a Dn graph to have every vertex along the cycle connected to P2. Each extended vertex that lies from the cycle has a degree of one. Given our existing knowledge of the P2 graph, we know that is has X(P2) = 2. This means that the attached P2 graph only requires one color not in common with the vertex it is adjacent to. Because of this, we are able to understand that the P2 graphs will not affect the chromatic number already established by the Cn subgraph.
Creating an Infinite Graph
With this done, we can investigate vertex coloring further, this time in relation to what is known as an infinite graph. An infinite graph can be defined as a graph in which there is not a finite amount of vertices. We created an infinite graph by placing an edge between an arbitrary vertex extended from the P2 portion of Dn to another arbitrary vertex extended from the P2 portion of a Dn + 1 graph. From this, we state that the graphs of Dn can be connected in this way to become an infinite graph.
Coloring an Infinite Graph
We can refer to our knowledge of the Dn graph to demonstrate that this is in fact true. We are able to attach an edge between one vertex of Dn graph to a vertex on a Dn + 1 graph without changing the chromatic number. This can be done because the pattern of cycle subgraphs for every Dn graph results in a chromatic number of 2,3,2,3, .... This means that as we move from graph to graph on the infinite graph, there is always an available color.
Discussion
In our research, the primary goal was to further explore graph properties and vertex colorings. Although we completed this, due to time constraints, we were unable to investigate more aspects of graph colorings and infinite graphs. A possible direction within this would be to be able to look at algorithms that determine chromatic number. As of right now, there are no possible algorithms that determine the minimum number of colors on a graph. In addition, if allowed more time, we would have liked to work with variations of infinite graphs to determine the properties that result from them. Another possibility in this research would also be to look at labelings such as harmonious and graceful labelings