What is Graph Theory?
Graph theory is the study of graphs. A graph is a structure that shows connections between certain items on the graph. It can be the backbone of a lot of algorithms.
In this section, there won’t be many algorithms. This part is more mathematical; there will be an article on graphs soon.
Graph Terminology
Clique and Independent Sets
Clique
A clique, in general, is a subgraph that is complete. A complete graph is a graph in which all vertices are connected to each other. It can be thought of as a friend or a group where everyone knows each other directly. The size of the clique is determined by the number of verticies included in the clique.
Cliques can also be defined as maximal and maximum. A maximal clique is a clique that cannot be made bigger. If the clique has three nodes and it is impossible to add another one while maintaining the clique rule, then it is a maximal clique of size 3. Maximal does not imply it is the biggest clique. The maximum clique is the clique of the greatest size. By that definition, it is also a maximal clique.
If the clique of the graph is requested, the maximum clique should be the response.
Independent Sets
An independent set is the exact opposite. An independent set of a graph is a set of verticies on the graph that are not adjacent to each other. It can be thought of as a group of people where everyone else is a stranger.
Very similar to the clique independent set can also be maximal and maximum. Maximal means that the independent set cannot be improved upon. While the maximum independent set implies it is of maximum size, Which also makes the maximum independent set a maximal independent set.
If the independent set of a graph is requested, the maximum independent set should be the response.
Vertex Cover
A vertex cover is a set of vertices in a graph where all edges are covered. Each vertex covers all of the edges connecting it directly to other nodes. Basically, every edge is connected to at least one of the verteices in the set.
The minimum vertex cover is the set of vertices that is able to cover all edges with the least number of vertices.
Graph Theorems
Handshaking Lemma
The sum of all the degrees in the graph is always even.
Implies: If a group of people handshake each other. The number of people who shook hands an odd number of times is always even.
The Handshaking Lemma allows an easy solution to problems such as:
There are 9 total people, and each person handshakes 5 other people. Draw a possible graph.
The Handshaking Lemma proves that this isn’t possible. There were an odd number of people who shook an odd number of hands.
Ramsey Numbers
Proves that there must exist a clique or independent set of at least size k. For example, if there is a group of six people, there is either a group of people who all know each other (clique) or three strangers (independent set). The Ramsey number is denoted by R (size of clique, size of independent set). The example can be represented as R(3,3) =6.
Ramsey Number calculations get out of hand quickly, and R(6,6) at this point in time does not have a definite answer.
Konigs Theorem
Konig’s theorem states that in a bipartite graph, the maximum matching is equal to the number of vertices in the minimum vertex cover.
Hall’s Marriage Theorem
The Halls theorem states that in a bipartite graph, there will be no perfect matching if there is a subset in one disjoint set that, as a group, is connected to a smaller number of nodes in the other disjoint set.
Four Color
If an area is split into regions, it will only take at most four colors to fill in the area so that no two duplicate colors touch.
This doesn’t really apply to graph coloring, just region coloring. The maximum number of colors needed to color a graph will always be equal to the number of nodes in the graph. Since the graph is complete, a new color will be needed for every single vertex.