Assignment On Separation Of A Graph Theory

Running head: Graph theory
Graph theory
Name of the student
Name of the University
Authors’ note

Graph theory
2
1)
Let, assume that m ≥ n > 2, the separation of a graph R is basically a partition of R into two of
the vertexes that disjoint the rectangular grids in the graphs R1 and R2, A rectangular grid sub
graph S of R strips a highest path P(R, s, t) as well as is called as a strip if:
1. S is even-sized and is not a 1- rectangle.
2. S and R − S is a separation of R.
3. s, t ∈ R − S.
4. U(R, s, t) = U(R − S, s, t) + |S |,
The following figure shows that the problem can be divided by stripping. In this figure, two of
the non-incident edges e1 and e2 are parallel to each other. If each of the end vertexes of e1 is
adjacent to some of the end vertexes of e2.
2)
m*m grid graph, where m is not equal to n≥2
Or, mn number of vertices is not equal to 2mn – mn number of edges.

Graph theory
3
Let us, assume that D is the number of edges that can be deleted without disconnecting the Graph
G.
According to the definition, a disconnected graph is termed as a graph in that there will be no
path between any two of the nodes of the graph.
Let,
m = 3
n = 2.
Thus mn = 6 vertices
2*3*2 – 3 – 2 = 12 – 3 – 2 = 7
If, we delete the path between a, b and c, d the graph will remain connected as in this graph there
is a path between each node to each node.
3)
Where E is the number of edges. In a soccer ball, 12 pentagons are there. Thus, there are 5*12
number of edges.
And there are 20 hexagons. Thus, 6*20 no of edges are there.
As, each of the edges of the ball is shared by two pentagons.
Hence, the number of edges are:
E = ½ (6*20 + 5*12)
= ½ * 180