The Path is Not Always Clear

Ellen Wiencek

 

Seemingly simple concepts in mathematics can sometimes take years to prove. Eight different proofs were falsely published, showing that a circle divides a plane into two regions. It took centuries for mathematicians to even decide that 1+1=2

 Here, we're proving a sufficient and necessary condition on cut vertices of a graph. A cut vertex is one which, when taken away, divides the graph into two disconnected subgraphs. The condition states that the cut vertex must be on every path between each vertex in the two resulting subgraphs. Though seemingly straightforward, this proof actually requires some formal logic. 
 

THEOREM 3.1.5
 

Let G be a graph. A vertex v ε V(G) is a cut-vertex of G if and only if there exist vertices u and w, distinct from v, such that v is on every path from u to w in G.

Proof. First, we will prove that if v ε V(G) is a cut vertex of G, then there exist vertices u and w, distinct from v, such that v is on every path from u to w in G.

Let G be a graph, and let v be a cut vertex. By the definition of a cut vertex, when we remove v from G, the resulting graph G-v has more components than G. By Proposition 3.1.4, we know that G has at least two vertices that are not cut vertices. Note: Proposition 3.1.4 states: "If G is a graph on n>=2 vertices, then G has at least two vertices that are not cut-vertices. Let u, w ε V(G) be two such vertices that are not cut vertices. We can find u and w that belong to the same component of G, but belong to different components of G-v. In G, there exists a path from u to w. When we remove v, then u and w are in different components of G-v and have no path between them. Thus, v must be on every path from u to w in G.

Second, we will prove that if there exist vertices u and w, distinct from v, such that v is on every path from u to w in G, then v is a cut vertex of G.

Let u and w be two vertices of G such that every path between them goes through the vertex v. Then u and w must be in the same component of G. If we remove v, then there are no paths between u and w. Then u and w must be in two different components of G-v. Since u and v are in the same component of G, but in different components of G-v, then we know that G-v has more components than G. Thus, v is a cut vertex.

Thanks for reading. Check out Route 11  

"Rabat" by Ellen Wiencek