Graph theory

• How to Find a Vertex That Minimizes Total Distance in a Graph
  Find a graph vertex with the smallest sum of shortest-path distances using repeated breadth-first search, or a linear-time rerooting method for trees.
• Why You Cannot Connect 3 Dots to 3 Squares Without Crossings
  The three-dot, three-square puzzle requires drawing K3,3. Euler’s formula shows it needs nine edges, but a planar bipartite graph on six vertices allows at most eight.
• How to Find the Expected Squared Distance in a Random Walk
  For a random walk on a graph, calculate expected squared distance by weighting each squared graph distance by the probability of reaching that vertex.
• Draw All Connected 5-Vertex Graphs with Odd Distances
  The only connected graph on five vertices with odd distances between every distinct pair is K5, the complete graph with all ten edges.
• What Does a Graph with Three Triangle Components Have?
  A graph made of three disjoint triangles is 3K3: it has 9 vertices, 9 edges, 3 components, and several useful standard properties.
• Why Does a Tree with n Vertices Have n − 1 Edges?
  Prove that every finite tree with n vertices has n − 1 edges by induction, using the fact that each nontrivial tree has a leaf.
• Prove the Petersen Graph Is Nonplanar Using Euler's Formula
  Use Euler’s formula and the Petersen graph’s girth of 5 to show that a planar drawing would need at least 35 face-edge incidences, but has only 30.
• Can You Draw This Figure Without Lifting the Pen? (Euler Paths)
  A figure can be drawn in one stroke exactly when it is connected and has 0 or 2 points where an odd number of lines meet. How to check, and where to start.