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

  • Context: Undergrad 
  • Thread starter Thread starter Superyoshiom
  • Start date Start date
  • Tags Tags
    Edge Graph
Click For Summary
SUMMARY

The discussion centers on the relationship between edge connectivity and the number of edge disjoint paths in a graph, specifically referencing Menger's theorem. It is established that if a graph has x edge-disjoint u,v paths, then the graph is x-edge-connected, implying that the number of cut sets between any two vertices is also x. However, the discussion reveals uncertainty regarding the implications for vertex connectivity, as the number of edge disjoint paths alone does not provide sufficient information to determine it. The participants suggest exploring extreme examples to better understand these concepts.

PREREQUISITES
  • Menger's theorem
  • Graph theory fundamentals
  • Edge connectivity concepts
  • Vertex connectivity definitions
NEXT STEPS
  • Study Menger's theorem in detail
  • Explore examples of edge disjoint paths in various graph structures
  • Research the relationship between edge connectivity and vertex connectivity
  • Investigate extreme cases of graph connectivity
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in connectivity properties and their implications in network design.

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?
 

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 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 Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
6K
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
3K
Graduate Counting edge numbers in bipartite graphs
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K