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?
 

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

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

B 4-colours theorem can be proved visually
Replies
21
Views
1K
I Prove that a given graph contains a cycle using induction (Graph Theory)
Replies
7
Views
2K
I The number of intersection graphs of ##n## convex sets in the plane
Replies
2
Views
856
I A way to comprehend the geometry of a hypercube
Replies
2
Views
1K
I Circuits or edge-disjoint unions of circuits in a connected graph
Replies
1
Views
1K
I Finding if a subgraph of a minimal non-planar graph is maximal planar
Replies
1
Views
1K
I Question regarding degrees of a graph and its biconnected components
Replies
34
Views
4K
I Number of edges in a tree digraph
Replies
5
Views
2K
I Graph Theory: (proof)conditions for Euler Circuit in Digraph
Replies
1
Views
2K
Counting edge numbers in bipartite graphs
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top