University Graph Theory Homework Assignment: Problems and Solutions

This document presents solutions to a graph theory homework assignment, addressing several key problems. The first problem explores the longest path in an m x n grid graph. The second problem focuses on calculating the maximum number of edges that can be removed from an m x n grid graph without disconnecting it. The third problem involves determining the number of edges in a soccer ball graph. The fourth problem requires proving the non-existence of a 9-regular graph with 42 edges. Finally, the fifth problem explores the conditions for a graph to be connected. The solutions are explained with proper justification and include a bibliography of relevant resources. The assignment covers concepts such as grid graphs, regular graphs, graph connectivity, and edge and vertex relationships.

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

2Graph theory
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.

3Graph theory
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

4Graph theory
= 90.
4)
As per the questions, the d graph will consist the vertex that will have d degree.
If d = 9
Then, a 9 regular graph will consist at the vertices that will consist 9 degree each.
As per the rule, the number of the edges of the regular graph k with n vertex is = nk/2.
Thus, in the 9 regular graph, the number of the edges are:
(10*9)/2 = 45 ≠ 42. (Proved)
Thus, it has been proved that the no 9 regular graph will be consisting 42 edges.
5)
n ≥ 2, vertex
p ≥ 1 edges.
G = Graph
P> (n-2)/2
Connected graph.
According to the rule of connected graph, a graph will be termed as the connected graph if any of
the vertex of a graph has at least one path between them.
If, n ≥ 2
P ≥ 1

5Graph theory
(G) graph
Then, in order to be a connected graph, there need to be at least one edge between these two
vertexes. Thus, it is proved that
p > 2/2 = 1 where p ≥ 1
Then the graph G will be connected.

6Graph theory
Bibliography:
Benjamin, A., Chartrand, G., & Zhang, P. (2017). The fascinating world of graph theory.
Princeton University Press.
Broumi, S., Smarandache, F., Talea, M., & Bakali, A. (2016). An introduction to bipolar single
valued neutrosophic graph theory. In Applied Mechanics and Materials (Vol. 841, pp.
184-191). Trans Tech Publications.
Deo, N. (2017). Graph theory with applications to engineering and computer science. Courier
Dover Publications.
Franz, M., Lopes, C. T., Huck, G., Dong, Y., Sumer, O., & Bader, G. D. (2015). Cytoscape. js: a
graph theory library for visualisation and analysis. Bioinformatics, 32(2), 309-311.
Moon, J. W. (2015). Topics on tournaments in graph theory. Courier Dover Publications.
Nath, B. J. (2017). Applications of Graph Theory in Different Branches of Science. rn, 55, 7.
Trinajstic, N. (2018). Chemical graph theory. Routledge.