0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Anon E. Muss May 5 '16 at 22:57
  • $\begingroup$ take a path that does the entire circle (with the same beginning and end). Is it forbidden? $\endgroup$ – Vincent May 6 '16 at 9:40
  • $\begingroup$ Yeah, there are 2 internally disjoint paths. You can only have one. $\endgroup$ – Anon E. Muss May 6 '16 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.