Question 1.
In a hostel, there are around ‘n’ number of students (assume a number above 100 for n)
with rooms categorized as triple, double, and single occupancy. Explain how you will
represent the above data as a graph.
(i) Will the graph be a simple graph or a multigraph?
Simple graph: A simple graph is an undirected graph with no loops or multiple edges
(Graph Theory-Discrete Mathematics (Types of Graphs), n.d.).
Multigraph: A graph that has several edges connecting the same set of vertices. It
has formed loops (Graph Theory-Discrete Mathematics (Types of Graphs), n.d.).
I've opted to utilize Students as the vertices rather than Rooms. The selection
can be made between students or rooms to depict the vertices of the graph.
Vertex Representation: Each vertex represents an individual student residing
in the hostel. Students are the entities depicted by vertices in the graph.
 Edge Representation: Edges between vertices (students) indicate
relationships such as roommates or students sharing the same room.
Connections (edges) represent the occupancy or adjacency between students
within the hostel.

 Graph Type: It could be a simple graph if focusing on one connection
(edge) between any two distinct students, assuming a single student occupies a
single room and doesn't share with multiple others. Each student vertex
connects to others based on their room-sharing arrangement or interactions
within the hostel.
 Room Allocation: Room allocation information can be inferred from the
connections between students. For instance, if students A and B share an edge,
they might be roommates or share the same room.
(ii) Will it have loops?
According to Weisstein (n.d.), “A loop of a graph is a degenerate edge that joins a
vertex to itself, also called a self-loop. A Simple graph cannot contain any loops.”
When representing students as vertices in a hostel graph, loops, which indicate
a student is connected to themselves, are typically omitted. This scenario
indicates that a student has their own room, which is unusual in a dormitory
setting. Loops are thus unlikely in a student-vertices graph because a student
cannot be assigned to themself in the graph, just as rooms cannot be assigned
to themselves. Furthermore, because the graph shows links between students
and rooms, it is a simple graph that precludes the appearance of loops. As a
result, there are no loops in this graph portraying students as vertices in a
dormitory setting.

(iii) What is the possible maximum and minimum degree for each student?
Minimum Degree:
o The minimum degree for a student vertex is typically 0 if the student
is not connected to any room (vertex).
o However, in a typical hostel scenario where each student occupies at
least one room, the minimum degree for each student would be 1,
indicating their connection to a room (vertex).
Maximum Degree: If each student can occupy only one room, the maximum
degree for each student would be 1, as a student can connect to only one room
(vertex). The rooms, conversely, can exhibit a maximum degree of 3 and a
minimum degree of 0, indicating instances where no students occupy the
room.
(iv) If all problems are represented in the form of graphs, won’t the problems be
easily visualized and solved?
 Graphs serve as potent tools for visually representing problems, yet their setup
and solution often demand extensive computations. As the number of vertices
and edges increases, the computational complexity of solving the problem
also escalates. When dealing with an exceedingly large number of vertices,
solving problems using graphs becomes impractical due to the sheer
computational demands involved.

 So, not all problems are easily converted into graph structures, nor can graphbased representations benefit all problems equally. Due to their complexity or
intrinsic structure, some problems may necessitate alternate modeling
methodologies or may be difficult to visualize using graphs.
 While graphs can be excellent problem-solving and visualization tools in
some situations, the applicability and effectiveness of graph-based solutions
are dependent on the nature and characteristics of the problem at hand.
(v) Can we represent every problem with a graph? Explain the reason by
considering an example of a situation that has 11 vertices such that the degree of
each vertex is 11.
 Not every problem can be effectively represented by a graph. Graphs are
useful for modeling and visualizing relationships among entities, but not all
scenarios translate seamlessly into a graph representation (Levin, n.d.).
 Consider the following scenario: a situation with 11 vertices, each with a
degree of 11, indicates a full network. Every vertex in a complete graph is
connected to every other vertex, resulting in a dense and highly interconnected
structure. A complete graph with 11 vertices (denoted as K11) has 55 edges
since each of the 11 vertices is connected to the other 10 vertices.


 Let’s represent this Mathematically:
K 11=(V , E)
o V represents the set of vertices, which contains 11 elements (V = {v1,
v2, v3, ..., v11}).
o E represents the set of edges, which contains all possible edges
between the vertices.
o Using the formula: E=
(n×(n−1))
2
: where n is the number of vertices.
n =11
o E=¿ ¿
E=
(11×10)
2
E=
(110)
2
E = 55

Question 2.
A University is conducting a conference for two days on different subjects for students
pursuing their higher education. Your task is to create a time slot scheduling model for the
conference sessions (based on the subjects attended by students) using graph coloring.
Draw the graph for the same and answer the chromatic number of this problem of
scheduling time slots with the number of subjects of your choice.
If we consider 4 subjects with 4 sessions each, leading to a total of 16 sessions per day for two
days (32 sessions in total), and edges between vertices represent students attending both sessions,
the graph representation could look like this:

**graph here**


Let's denote the subjects as A, B, C, and D, and their sessions as A1, A2, A3, A4, B1, B2, B3,
B4, C1, C2, C3, C4, D1, D2, D3, and D4.
 Vertices A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, D1, D2, D3, and D4 represent
the sessions for the respective subjects.
 Edges between vertices indicate students attending both sessions connected by the edge.
For example, A1 and A2, A1 and B1, A1 and B2, etc., have edges representing students
attending both connected sessions.
This graph illustrates the connections between sessions, showing where students attend multiple
sessions across the four subjects. Each vertex represents a specific session, and the edges
between them indicate student attendance in both sessions.



Question 3.
 Explain Euler and Hamiltonian cycles and provide one simple counter example for each.
Find the Euler circuit/path and Hamiltonian cycle/path for the given graph G

**graph here**

According to (GeeKsForGeeks, n.d.), “Eulerian Path is a path in graph that visits every
edge exactly once. Eulerian Circuit is a Eulerian Path which starts and ends on the same
vertex.”
“Hamiltonian Cycle or Circuit in a graph G is a cycle that visits every vertex of G exactly once
and returns to the starting vertex.” Hamiltonian Path in a graph G is a path that visits every
vertex of G exactly once and Hamiltonian Path doesn’t have to return to the starting vertex. It’s
an open path. (GeeKsForGeeks, n.d.),


Find the Euler circuit/path and Hamiltonian cycle/path for the given graph G.
Euler circuit: No Cycle
 Euler Path: 6→7→3→2→1→4→6→5→2→4 →5→3
(Introduction to Euler Paths and Euler Circuits, n.d.)
Hamiltonian Cycle: 1→2→3→7→6→5→4 →1
Hamiltonian Path: 1→2→3→5→4 →6→7
(Introduction to Hamilton Paths and Hamilton Circuits, n.d.).

Question 4:
 Explain the spanning tree. Find at least two possible spanning trees for the following
graph H and explain how you determined that they are spanning trees. Draw a bipartite
graph from any one of the two spanning trees that you found.

**graph here** 


As noted by Lippman (2020), A spanning tree is a connected graph that includes all vertices and
has no cycles. In simpler terms, it's a graph where there's a path between any two vertices, but
no loops or cycles exist within it.
Spanning Tree H1: 3−6, 3−2,2−5, 2−1 , 1−4

**graph here**

Spanning Tree H2: 3−2,2−1, 2−5 ,5−4 ,5−6

**graph here**


(Introduction to Spanning Trees, n.d.).
Draw a bipartite graph from any one of the two spanning trees that you found.
Bipartite Graph of Spanning Tree H2:

**graph here**

A Bipartite Graph is a graph that can be divided into two distinct sets, known as Bipartite Sets,
where edges exclusively link vertices from one set to vertices in the other set. This type of graph
lacks edges connecting vertices within the same set (Prepbytes, 2023).

References:
Canva. (2023). Canva. https://www.canva.com/
Eulerian path and circuit for undirected graph. (2013, June 13). GeeksforGeeks.
https://www.geeksforgeeks.org/eulerian-path-and-circuit/
Graph Theory-Discrete Mathematics (Types of Graphs). (n.d.). BYJUS.
https://byjus.com/maths/graph-theory/
Introduction to Euler Paths and Euler Circuits. (n.d.). Www.youtube.com; Mathispower4u.
Retrieved January 3, 2024, from https://www.youtube.com/watch?v=J6O9kis_pTw
Introduction to Hamilton Paths and Hamilton Circuits. (n.d.). Www.youtube.com;
Mathispower4u. Retrieved January 3, 2024, from https://www.youtube.com/watch?
v=UOE22pyKD5c
Introduction to Spanning Trees. (n.d.). Www.youtube.com; Mathispower4u. Retrieved January
3, 2024, from https://www.youtube.com/watch?v=fO-R1vwgsmw
Levin, O. (n.d.). Definitions. In discrete.openmathbooks.org.
https://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html
Lippman, D. (2020, January 22). 6.7: Spanning Trees. Mathematics LibreTexts.
https://math.libretexts.org/Bookshelves/Applied_Mathematics/Math_in_Society_(Lippman)/
06%3A_Graph_Theory/6.07%3A_Spanning_Trees
Prepbytes. (2023, March 24). Bipartite Graph. PrepBytes Blog.
https://www.prepbytes.com/blog/graphs/bipartite-graph-and-example/
Weisstein, E. W. (n.d.). Graph Loop. Mathworld.wolfram.com.
https://mathworld.wolfram.com/GraphLoop.html


rewrite all this including references and in text citations.