# Connectivity and internally disjoint paths.

Can anyone give me an example of a graph with vertex connectivity = $1$, edge connectivity = $3$, and minimum degree = $4$?

Also, I'm looking for a $2$-connected graph with a $uv-$path from which no other $uv-$path is internally disjoint (both edge and vertex disjoint)?

Thanks!

## 1 Answer

For the first one, take two $K_5$ (complete graph with 5 vertices), add one node in the middle, which you connect to three vertices of one of the $K_5$ and three of the other $K_5$.

Edge connectivity is $3$ and removing the middle node disconnects the graph.

For the second one, take a hamiltonian circle.

• Thanks for that first one, but the second one - how does that follow the "no other path is disjoint" if the paths are disjoint? Am I reading the question incorrectly? – Anon E. Muss May 5 '16 at 22:57
• take a path that does the entire circle (with the same beginning and end). Is it forbidden? – Vincent May 6 '16 at 9:40
• Yeah, there are 2 internally disjoint paths. You can only have one. – Anon E. Muss May 6 '16 at 11:46