Simple Graphs
Research in graph theory has revolved around the study of various graphs by mathematicians. We will look at three graphs: paths, cycles and complete graphs, to determine their characteristics.
Path Graphs
A path graph, can be denoted Pn, where n is the number of vertices, is a graph where every vertex (besides the starting and ending vertex which have a degree of one) have degree two. All of these graphs can be represented as straight lines in the plane. After a brief repetition of this process, we are able to see a defining pattern of this graph where there is in fact a correlation of number of vertices to degrees. As the number of vertices increase in size, the number of edges increases as well. This relationship can be expressed where the number of edges will always be one less than the number n of vertices.
Cycle Graphs
We can also look at a cycle graph which is denoted as Cn where n is the number of vertices present in the graph. In this graph, every vertex must have a degree of two. Because of this, C1 and C2 graphs are not possible. In addition, the graph must be adjacent between every pair of vertices.
Complete Graphs
A complete graph is one which can be denoted Kn where n is the number of vertices. In this graph, each vertex must be adjacent to each other.
Vertex Coloring
Investigating these family graphs gives us a basic understanding of how graphs vary from one to the other. With this knowledge, we can impose vertex coloring onto them.
Coloring a Path Graph
We can color an arbitrary vertex on the graph red. We can color the adjacent vertex green. Because the next vertex isn’t adjacent to the already red vertex, it can also be colored red. A subgraph (or smaller graph present within the graph) there is a P2. Because of this, we know the chromatic number has to be at least two. In addition, we know that it can’t be any more than this because a subgraph with a larger chromatic number is not present.
Coloring a Cycle Graph
We can pick an arbitrary vertex on the graph and color it red. After this, we can identify the two other present adjacent vertices and color them green. After this we are left with one final option, the vertex is adjacent to two already green vertices, therefore, it can only be colored with red. The C4 would have a chromatic number of two. We know that it can be no less than this because it contains vertices that are are adjacent to each other.
Coloring a Complete Graph
We can start the vertex coloring by applying a color to an arbitrary vertex on the graph. When we look a the adjacent vertices on the graph, we have to take into consideration that every vertex is connected to each other. As a result of this, when we color the graph, we have to use a new color for every vertex. The chromatic number has to be equivalent the number of vertices because of this.