Summary
Summary Graph theory
- Course
- Institution
- Book
IT helps you to understand briefly about the graph theory in discrete mathematics
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
AMS 301 Cheat Sheets Full Course
Seller
Follow
gnanasekarg
Content preview
SCHOOL OF SCIENCE AND HUMANITIESDEPARTMENT OF MATHEMATICS
UNIT – I – Advanced Graph Theory – SMT5207
1
, I. Connectivity
Contents - Connectivity and edge-connectivity – 2-connected graphs – Menger’s theorem.
Connectivity
A graph is said the connectivity of a graph. A graph with multiple disconnected
vertices and to be connected if there is a path between every pair of vertex. From
every vertex to any other vertex, there should be some path to traverse. That is called
edges is said to be disconnected.
Example 1
In the following graph, it is possible to travel from one vertex to any other vertex.
For example, one can traverse from vertex ‘a’ to vertex ‘e’ using the path ‘a-b-e’.
Example 2
In the following example, traversing from vertex ‘a’ to vertex ‘f’ is not possible
because there is no path between them directly or indirectly. Hence it is a
disconnected graph.
Cut Vertex
Let ‘G’ be a connected graph. A vertex V ∈ G is called a cut vertex of ‘G’, if ‘G-V’
(Delete ‘V’ from ‘G’) results in a disconnected graph. Removing a cut vertex from
a graph breaks it in to two or more graphs.
Note − Removing a cut vertex may render a graph disconnected. A
connected graph ‘G’ may have at most (n–2) cut vertices.
Example
In the following graph, vertices ‘e’ and ‘c’ are the cut vertices.
2
,By removing ‘e’ or ‘c’, the graph will become a disconnected graph.
Cut Set of a Graph
Let ‘G’= (V, E) be a connected graph. A subset E’ of E is called a cut set of G if
deletion of all the edges of E’ from G makes G disconnect.
If deleting a certain number of edges from a graph makes it disconnected, then those
deleted edges are called the cut set of the graph.
Example
Take a look at the following graph. Its cut set is E1 = {e1, e3, e5, e8}.
After removing the cut set E1 from the graph, it would appear as follows −
Similarly, there are other cut sets that can disconnect the graph −
E3 = {e9} – Smallest cut set of the graph.
E4 = {e3, e4, e5}
Edge Connectivity
Let ‘G’ be a connected graph. The minimum number of edges whose removal makes
‘G’ disconnected is called edge connectivity of G.
Notation − λ(G)
In other words, the number of edges in a smallest cut set of G is called the edge
connectivity of G.
3
, If ‘G’ has a cut edge, then λ(G) is 1. (edge connectivity of G.)
Example
Take a look at the following graph. By removing two minimum edges, the connected
graph becomes disconnected. Hence, its edge connectivity (λ(G)) is 2.
Here are the four ways to disconnect the graph by removing two edges −
Vertex Connectivity
Let ‘G’ be a connected graph. The minimum number of vertices whose removal
makes ‘G’ either disconnected or reduces ‘G’ in to a trivial graph is called its vertex
connectivity.
Notation − K(G)
Example
In the above graph, removing the vertices ‘e’ and ‘i’ makes the graph disconnected.
If G has a cut vertex, then K(G) = 1.
Notation − For any connected graph G,
Vertex connectivity (K(G)), edge connectivity (λ(G)), minimum number of degrees
of G(δ(G)).
Theorem (Whitney) For any graph G, κ(G) ≤ λ (G) ≤ δ (G).
Proof: We first prove λ(G) ≤ δ(G).
If G has no edges, then λ = 0 and δ = 0. If G has edges, then we get a disconnected
graph, when all edges incident with a vertex of minimum degree are removed. Thus,
in either case, λ (G) ≤ δ (G).
We now prove κ(G) ≤ λ (G). For this, we consider the various cases. If G
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller gnanasekarg. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67096 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now