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

  • I
  • Thread starter Superyoshiom
  • Start date
  • Tags
    Edge Graph
In summary, the number of edge disjoint paths in a graph is an indication of the edge connectivity, but it does not provide information about the vertex connectivity. This can be seen by considering extreme examples where the graph has a high number of edge disjoint paths but a low vertex connectivity.
  • #1
Superyoshiom
29
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
  • #2
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?
 

1. What is edge connectivity of a graph?

Edge connectivity of a graph refers to the minimum number of edges that must be removed in order to disconnect the graph into two or more separate components.

2. How is edge connectivity related to the number of edge disjoint paths?

The edge connectivity of a graph is equal to the maximum number of edge disjoint paths that can be found between any two vertices in the graph.

3. Can the edge connectivity of a graph be greater than the number of vertices?

No, the edge connectivity of a graph cannot be greater than the number of vertices. This is because each vertex can only be connected to a maximum of (n-1) other vertices, where n is the number of vertices in the graph.

4. How is the edge connectivity of a graph calculated?

The edge connectivity of a graph can be calculated using various algorithms, such as the Ford-Fulkerson algorithm or the Edmonds-Karp algorithm. These algorithms use a maximum flow approach to find the minimum number of edges that need to be removed to disconnect the graph.

5. Can the edge connectivity of a graph change?

Yes, the edge connectivity of a graph can change if edges are added or removed. It can also change if the weight of edges is modified, as this can affect the minimum number of edges that need to be removed to disconnect the graph.

Similar threads

I A way to comprehend the geometry of a hypercube
    • General Math
Replies
2
Views
310
B 4-colours theorem can be proved visually
    • General Math
Replies
21
Views
1K
I The number of intersection graphs of ##n## convex sets in the plane
    • General Math
Replies
2
Views
692
I Circuits or edge-disjoint unions of circuits in a connected graph
    • Topology and Analysis
Replies
1
Views
793
I Prove that a given graph contains a cycle using induction (Graph Theory)
    • General Math
Replies
7
Views
2K
I Question regarding degrees of a graph and its biconnected components
    • General Math
Replies
34
Views
4K
I Number of edges in a tree digraph
    • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
I Graph Theory: (proof)conditions for Euler Circuit in Digraph
    • General Math
Replies
1
Views
2K
I Finding the dependence of maximum vertex degree on k-colorability
    • General Math
Replies
1
Views
1K
MHB Graph: showing that diameter is greater than average pairwise distance
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K

Hot Threads

Recent Insights

Back
Top