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

  • Thread starter Thread starter Superyoshiom
  • Start date Start date
  • Tags Tags
    Edge Graph
Click For Summary
The discussion centers on the implications of having a specific number of edge disjoint paths in a graph, denoted as x. It references Menger's theorem, suggesting that if there are x edge disjoint paths between two vertices, the graph is x-edge-connected and has x cut sets. However, the participants express uncertainty about deriving information on vertex connectivity solely from edge disjoint paths. The conversation also hints at the need for extreme examples to better understand the limitations of these inferences. Ultimately, the relationship between edge and vertex connectivity remains complex and not fully determined by the number of edge disjoint paths alone.
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?
 

Thread 'Leibniz Rule Videos on Digital-University'

Good morning I have been refreshing my memory about Leibniz differentiation of integrals and found some useful videos from digital-university.org on YouTube. Although the audio quality is poor and the speaker proceeds a bit slowly, the explanations and processes are clear. However, it seems that one video in the Leibniz rule series is missing. While the videos are still present on YouTube, the referring website no longer exists but is preserved on the internet archive...
View full post »

Similar threads

High School 4-colours theorem can be proved visually
  • · Replies 21 ·
Replies
21
Views
2K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad A way to comprehend the geometry of a hypercube
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Circuits or edge-disjoint unions of circuits in a connected graph
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Counting edge numbers in bipartite graphs
  • · Replies 1 ·
Replies
1
Views
1K
MHB Graph: showing that diameter is greater than average pairwise distance
  • · Replies 4 ·
Replies
4
Views
3K