Image source: Quanta Magazine
Below is an example we worked out together of how to write a clean proof.
Claim: In a graph with \(n\) vertices, if \(\delta +\Delta \ge n-1\), then the graph is connected.
Proof: The highest degree vertex in the graph has \(\Delta\) edges. So the component containing the highest degree vertex has at least \(\Delta +1\) vertices.
Assume that there is another connected component. The lowest degree vertex within that component has at least \(\delta\) edges. So this second component has at least \(\delta +1\) vertices. So the whole graph has at least \((\Delta + \delta) + 2\) vertices. Since \((\Delta + \delta) \ge n-1\), it follows that the graph has at least \(n+1\) vertices. This is a contradiction, which proves that the graph can only have one connected component. Therefore the graph is connected. \(\square\)
Today in class we wrote the following Sage/Python program to count and display all of the graphs on 5 vertices with up to 5 edges:
Image source: Quanta Magazine
Today we talked about the problem of deciding if two graphs are isomorphic. A naive way to tell would be to check all \(N!\) ways to relabel the graphs to see if they are equivalent. There are much better algorithms, and this article gives an overview of the problem and describes some fascinating new research:
Quanta Article on Graph Isomorphism Problem