My question is this:
Which graphs remain connected when any path is removed? For example, complete graphs, $K_n$, fulfill this. Another example are the cyclic graphs, $C_n$. Can someone give an example of another that is neither cyclical nor complete?
Thanks.
On
It seems that for any integer $n\geq1$ the complete bipartite graph $K_{n,n}$ has this property.
Indeed, if $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ are parts of this graph, then any path in it has the form $xa_{i_1}b_{i_2}\ldots a_{i_k}b_{i_k}y$, where $x$ is either empty or $x\in B$ and $y\in A$ or $y$ is empty. In any case, if more than one vertex remains after removing those vertices that are included in the path, then there will be at least one vertex from both $A$ and $B$ among the remaining vertices.
Suppose that $G$ is a connected $n$-vertex graph that remains connected when any path is deleted. Then it must be either $C_n$, $K_n$, or (when $n$ is even) $K_{n/2,n/2}$.
To prove this, let $P$ be a longest path of $G$, with endpoints $x$ and $y$. Then $x$ cannot have any neighbors outside $P$, or else the path could be made longer. Therefore deleting the path $P-x$ leaves $x$ isolated; in order for this not to disconnect $G$, it must be the case that $P$ is a Hamiltonian path. Also, deleting the path $P-\{x,y\}$ cannot disconnect $G$, so there must be an edge $xy$. Therefore $G$ contains a Hamiltonian cycle. Number the vertices of this Hamiltonian cycle as $v_1, v_2, \dots, v_n$ in order, and treat the indices as numbers mod $n$ (so that $v_{n+1}=v_1$, and so on). One possibility is that $G$ has no edges out of the cycle; this gives us $C_n$.
Otherwise, if $G$ also has some edge $v_i v_j$ outside the cycle, then there is a path $$v_{i+2}, v_{i+3}, \dots, v_j, v_i, v_{i-1}, \dots, v_1, v_n, v_{n-1}, \dots, v_{j+2}$$ which includes every vertex except $v_{i+1}$ and $v_{j+1}$; deleting this path does not disconnect $G$, so $G$ must also have the edge $v_{i+1} v_{j+1}$. By induction, if $G$ has any edge $v_i v_{i+d}$, then $G$ must have all $n$ of the edges $v_i v_{i+d}$ for $i=1, \dots, n$. (Call this the "shifting rule".)
Also, if $G$ has an edge $v_i v_j$ outside the cycle, then by the shifting rule, it has $v_{i+1} v_{j+1}$, so there is a second Hamiltonian cycle $$v_1, v_2, \dots, v_i, v_j, v_{j-1}, \dots, v_{i+1}, v_{j+1}, v_{j+2}, \dots, v_n, v_1.$$ On this Hamiltonian cycle, vertices $v_{i-1}$ and $v_{j-1}$ are $3$ steps apart, so by the shifting rule, all edges $3$ steps apart are present. Let's number the vertices of this other cycle $w_1, w_2, \dots, w_n$ in order, with the same conventions; the new cycle has every edge of the form $w_i w_{i+3}$.
For any $i$ and $j$, we have a path $$w_{i+1}, w_{i+2}, \dots, w_{j-1}, w_{j+2}, \dots, w_n, w_1, \dots, w_i$$ which includes every vertex except $w_i, w_j, w_{j+1}$; therefore $w_i$ must be adjacent to either $w_j$ or $w_{j+1}$. Moreover, if $w_i$ is ever adjacent to both $w_j$ and $w_{j+1}$, then $$w_{i-1}, w_{i+2}, \dots, w_j, w_i, w_{j+1}, \dots, w_n, w_1, \dots, w_{i-1}$$ is a cycle including all vertices except $w_{i+1}$. Deleting any vertex $x$ whatsoever from it creates a path through every vertex except $w_{i+1}$ and $x$; therefore $w_{i+1}$ must be adjacent to every vertex. By the shifting rule, all vertices are adjacent: the graph is complete.
If $w_i$ is not ever adjacent to both $w_j$ and $w_{j+1}$, then it must alternate: $w_i$ is adjacent to $w_{i+3}, w_{i+5}, w_{i+7}, \dots$. By the shifting rule, every vertex must be adjacent to every other vertex an odd number of steps around the cycle. If $n$ is odd, this would give us the complete graph again; for even $n$, it gives us the complete bipartite graph $K_{n/2,n/2}$, our final case.