Edge connectivity of a graph given the number of edge disjoint paths

  • Level: Undergrad 
  • Thread starter Thread starter Superyoshiom
  • Start date Start date
  • Tags Tags
    Edge Graph
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
1 reply · 2K views
Superyoshiom
Messages
29
Reaction score
0
What can we infer about the connectivity and edge connectivity of a graph given the number of edge disjoint paths?

So the number of edge disjoint u,v paths in a graph is x. Doing this problem, I thought back to Menger's theorem, and thought that the graph is x-edge-connceted and so the number of cut sets between any two vertices is also x. However I'm not sure how to find find out anything about the vertex connectivity since all I was given was the number of edge disjoint paths.
 
Mathematics news on Phys.org
Superyoshiom said:
number of cut sets
Do you mean minimal size of cut sets?
Superyoshiom said:
However I'm not sure how to find find out anything about the vertex connectivity since all I was given was the number of edge disjoint paths.
Perhaps it doesn’t tell you much about connectivity. What extreme examples can you construct?