Broken Graphs, Part I

Is it possible for graphs to come in individual pieces? Is it possible to take a graph and break it into multiple pieces? What implications does this have in real world applications?

What You Should Learn

  • The difference between a connected graph and a disconnected one.
  • How connected graphs can be turned into disconnected ones.
  • The terms used to describe special classes of graphs that can be broken by removing one element.
cracked glass

Connected means exactly what the English word suggests. Two points are connected if there's a path from one to the other. A graph is connected if it has only "one piece".

All that business about "a function that maps ..." just means that each edge is assigned a number.

Both of the graphs below are disconnected. It's obvious that the first one is because it's made up of two completely distinct pieces. (If you want a technical reason it's disconnected because there's no path from v1 to v3, among others.) The second graph is a little less clear because of the way the graphs overlap but, if you look closely, you'll see that there's no path from v5 to v8.

graph 15 graph 16

If G is a graph and e is an edge in G then G - e is G with edge e removed. Similary if v is a vertex of G then G - v is G with the vertex v and every edge that connected to it removed. Now assume that G is connected. If G - e is disconnected then e is called a bridge. If G - v is disconnected then v is called a cut-vertex.

The subtraction symbol, - , has the same idea of "taking away" with graphs that it does with numbers. G - e means the graph G with edge e "subtracted" or "taken away". The same idea applies to vertices only you also have to take away all of the edges that connected to the vertex. A graph theory bridge is also similar to its English equivalent. You can think of it as a connector between two graphs that would be disconnected if the bridge weren't there. Just like two islands become disconnected if the bridge connecting them is removed.

Broken Graphs, Part II >><< Hamiltonian Graphs, Exercises