# Constructing Minimally 3-Connected Graphs
## 2 Terminology, Previous Results, and Outline of the Paper  
We begin with the terminology used in the rest of the paper. Since graphs used in the paper are not necessarily simple, when they are it will be specified. Let \(G\) be a graph and \(e=uv\) be an edge with end vertices \(u\) and \(v\). The graph with edge \(e\) deleted is called an _edge-deletion_ and is denoted by \(G\backslash e\) or \(G\backslash uv\). When deleting edge \(e\), the end vertices \(u\) and \(v\) remain. To contract edge \(e\), collapse the edge by identifing the end vertices \(u\) and \(v\) as one vertex, and delete the resulting loop. The graph with edge \(e\) contracted is called an _edge-contraction_ and denoted by \(G/e\). A graph \(H\) is a _minor_ of a graph \(G\) if \(H\) can be obtained from \(G\) by deleting edges (and any isolated vertices formed as a result) and contracting edges. We write \(H=G\backslash X/Y\), where \(X\) is the set of edges deleted and \(Y\) is the set of edges contracted. A _triangle_ is a set of three edges in a cycle and a _triad_ is a set of three edges incident to a degree 3 vertex. A graph is 3-_connected_ if at least 3 vertices must be removed to disconnect the graph. In a 3-connected graph \(G\), an edge \(e\) is _detelable_ if \(G\backslash e\) remains 3-connected. A 3-connected graph with no deletable edges is called _minimally 3-connected_. There are multiple ways that deleting an edge in a minimally 3-connected graph \(G\) can destroy connectivity. One obvious way is when \(G\) has a degree 3 vertex \(v\) and deleting one of the edges incident to \(v\) results in a 2-connected graph that is not 3-connected. [PERSON] proved that a minimally 3-connected graph has at least one triad [5]. We exploit this property to develop a construction theorem for minimally 3-connected graphs. The operation that reverses edge-deletion is edge addition. A simple graph \(G\) with an edge \(e=uv\) added between non-adjacent vertices is called an _edge addition_ of \(G\) and denoted by \(G+e\) or \(G+uv\). The operation that reverses edge-contraction is called a vertex split of \(G\). To _split_ a vertex \(v\) with \(deg_{G}(v)\geq 4\), first divide \(N_{G}(v)\) into two disjoint sets \(S\) and \(T\), both of size at least 2. Then replace \(v\) with two distinct vertices \(v\) and \(v^{\prime}\), join them by a new edge \(f=vv^{\prime}\), and join each neighbor of \(v\) in \(S\) to \(v\) and each neighbor in \(T\) to \(v^{\prime}\). The resulting graph is called a _vertex split_ of \(G\) and is denoted by \(K=G\circ_{S,T}f\). In other words \(N_{G}(v)\) is partitioned into two sets \(S\) and \(T\), and in \(K\), \(N_{K}(v)=S\cup v^{\prime}\) and \(N_{K}(v^{\prime})=T\cup v\). Observe that \(deg_{K}(v)\geq 3\) and \(deg_{K}(v^{\prime})\geq 3\). We can get a different graph depending on the assignment of neighbors of \(v\) in \(G\) to \(v\) and \(v^{\prime}\) in the vertex split; hence the sets \(S\) and \(T\) in the notation. With a slight abuse of notation, we can say \(G\circ f\), as each vertex split is described with a particular assignment of neighbors of \(v\) in \(G\) to \(v\) and \(v^{\prime}\). When performing a vertex split, we will think of \(v^{\prime}\) as the new vertex that gets added and \(f=vv^{\prime}\) as the new edge that gets added. Observe that if \(G\) is 3-connected, then edge additions and vertex splits remain 3-connected. The degree condition \(deg_{G}(v)\geq 4\) is not necessary for an arbitrary vertex split, but required to preserve 3-connectivity. Figure 2 shows the vertex split operation. In 1961 [PERSON] proved that a simple graph is 3-connected if and only if it is a wheel or is obtained from a wheel by a finite sequence of edge additions or vertex splits. This result is known as Tutte's Wheels Theorem (1). Theorem 1 ([PERSON], 1961): _Let \(G\) be a simple graph that is not a wheel.