Graph Theory

graphs

1. Graph Theory
15UMTC53
III B.Sc Mathematics (SF)
G.Nagalakshmi
K.Muthulakshmi

2. Subgraphs
Types of Subgraphs
Walk, Path, Cycle
Connected graphs
connectivity

3. Subgraphs
A subgraph of a graphG=(V(G),E(G)) is a graph
H=(V(H),E(H)) with V(H) V(G) and V(H) V(G).
We also say that G contains H. 

4. Subgraphs -Example
G=(V,E)
VG ={1,2,3,4}
EG = {a,b,c,d,e}
Let: U = {1,2,3}, W =
{2,3,4}, F = {b}, P =
{a,d}. Then (U,P)
and (W,F) are
subgraphs while
(U,F) and (W,P) are
not.
1
3 4
2
a
e
c b
d

5. Spanning Subgraph
If H=(U,F) is a subgraph of G(V,E) and U = V, then H is
called a spanning subgraphof G.

6. Trivial Subgraph
Subgraph H is trivial, if either H = f, or H = G.

7. Induced Subgraph
Graph H is an induced
subgraph of graph G, if H is
obtained from G by
removing the vertices from
V(G)-V(H).
An induced subgraph of G is
determined by its vertrex
set U µV(G). If we want to
distinguish the graph from
its vertex set we denote the
former by <U> or, if we wnat
to refer to the original
graph by G|U.
Example:P
5is an induced
subgraph of C
6.

8. Walk, Path and cycle
An edge progression W inG is a sequence
v
1,e
1,v
2,e
2,…,v
k,e
k, v
k+1 such that k ≥ 0, and e
i=(v
i,
v
i+1)∈E(G) for i=1,…,k.
If in addition e
i ≠ e
j for all 1≤i<j≤ k, W is called a walkin
G.
W is closedif v
1= v
k+1 .
A path is a graph P=({v
1,…,v
k+1 },{e
1,…,e
k}) such that v
i ≠
v
j for 1≤i<j≤ k+1,
fand the sequence
v
1,e
1,v
2,e
2,…,v
k,e
k,v
k+1is a walk.
A circuitor a cycleis a graph ({v
1,…,v
k },{e
1,…,e
k}) such
that the sequence v
1,e
1,v
2,e
2,…,v
k,e
k,v
1is a (closed) walk
and v
i ≠ v
j for 1≤i<j≤ k+1.
The lengthof a path or circuit is the number of its
edges.

10. Connected graphs
Let G be some undirected graph. Gis called
connectedif there is a v-w-path for all v, w 
V(G); otherwise Gis disconnected. The maximal
connected subgraphs of G are its connected
components. A vertex vwith the property that G –
v has more connected components thanG is called
an articulation vertex. An edge e is called a
bridgeif G –e has more connected components
thanG.

12. Distance in Connected Graph
Each connected graph G gives rise to a metric space
(V,d
G) for d
G(u,v) being the length of shortest path in
G, from u to v.

13. Connectivity

14. k-connectedness
Graph G with |V(G)| > k is k-
connected, if a removal of any set S
with |S| < k stays conneced.
Connectivityk(G) of graph G is the
largest k, such that G is still k-
connected.
Vertex v of graph G is a cut-vertex, if
W(G –v) > W(G ).
A connected graph with no cut-vertex
is called a block.

15. Definitions
Separating Set
Connectivity
k-connected –Connectivity is at least k
Induced subgraph –subgraph obtained by deleting a set
of vertices
Disconnecting set (of edges)

16. Definitions
Edge-connectivity - = Minimum size of a disconnecting
set
k-edge connected if every disconnecting set has at least k edges
Edge cut –

17. Examples
Consider a bipartition X, Y of
Since every separating set contains
either X or Y which are themselves a
separating set,
[1]

18. Examples
Harary [1962]

19. Example of Edge Cut

20. Definitions
Block –A maximal connected subgraph of G that has no
cut-vertex.