GRAPH THEORY & FUNCTIONS – 5 MARK IMPORTANT ANSWERS (BCA SEM 1)
1. Union of P3 and K5:
The union of two graphs combines all vertices and edges from both graphs without merging parallel
edges. P3 is a path with three vertices connected sequentially. K5 is a complete graph with 5
vertices. Their union contains 8 vertices and includes all edges from both structures. It illustrates
how two independent graphs can form a larger graph.
2. Four-Regular Bipartite Graph:
A bipartite graph divides vertices into two disjoint sets such that no edges connect vertices within
the same set. A 4-regular bipartite graph means every vertex has degree 4. An example is K4,4,
where each vertex in the left set is connected to all 4 vertices in the right set.
3. Complete Binary Tree:
A complete binary tree is a binary tree in which all levels except possibly the last are fully filled, and
nodes in the last level are as far left as possible. Example: A tree with root A, children B and C, and
B having children D and E.
4. Complete Graph:
A complete graph is one in which every pair of distinct vertices is connected by a unique edge. K4
contains 4 vertices and 6 edges. Complete graphs are maximally connected and important in graph
theory due to their high edge density.
5. Graph Isomorphism:
Two graphs are isomorphic if there exists a one-to-one correspondence between their vertices that
preserves adjacency. Isomorphic graphs look different visually but have identical structure.
Example: Two triangles with differently named vertices.
6. Walk, Path, Trail:
Walk – sequence of vertices where each adjacent pair is connected by an edge.
Path – a walk with no repeated vertices.
Trail – a walk with no repeated edges.
7. Minimum Spanning Tree:
In a weighted graph, a minimum spanning tree (MST) is a spanning tree with the minimum total
edge weight. MSTs are used in network design, clustering, and optimization.
8. Handshaking Theorem:
States that the sum of degrees of all vertices in a graph equals twice the number of edges. Used to
prove results like “number of odd-degree vertices is even.”
9. Travelling Salesman Problem:
TSP asks for the shortest route that visits each city exactly once and returns to the start. It is
NP-hard and solved using approximation or dynamic programming.
10. Prim’s Algorithm:
Starts with any vertex and repeatedly adds the smallest edge connecting the growing tree to a new
vertex until all vertices are included.
11. Simple Graph:
A graph with no loops or parallel edges. It is the basic structure in graph theory.
12. Hamiltonian:
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle returns to the starting
vertex. Used in optimization and routing.
13. Colouring Problem:
Assign colours to vertices such that adjacent ones have different colours. Minimum number of
colours needed is the chromatic number.
14. Graph Operations:
Union – combines vertices and edges.
Intersection – includes only common edges.
Complement – flips edges: every missing edge becomes present.
15. Self-Complementary Graph:
A graph isomorphic to its complement. Example: A 4-vertex cycle C4.
16. Properties of Trees:
Acyclic, connected, has n−1 edges for n vertices, and has a unique path between every pair of
vertices.
17. Matrix Representation:
Adjacency matrix shows which vertices are connected. Incidence matrix shows edge–vertex
relationships.
18. Complete Bipartite Graph:
Has two sets of vertices; each vertex in one set is connected to all in the other. Example: K3,2.
19. Connectivity:
Vertex connectivity = minimum vertices needed to disconnect the graph.
Edge connectivity = minimum edges needed to disconnect the graph.
20. Tree with n Vertices Has n−1 Edges:
Proved using induction. Each added vertex requires exactly one edge to maintain acyclic
connectivity.
21. Unique Path Property:
A graph is a tree iff it is connected and has a unique path between every pair of vertices.
22. Kuratowski’s Theorem – K5 & K3,3 Non-Planar:
Both graphs contain subdivisions that make it impossible to draw without edge crossings, proving
they are non-planar.
23. Types of Functions:
Injective (one-one), Surjective (onto), Bijective (both). Functions map inputs to outputs based on
specific rules.
24. Bijective Function:
A function that is both injective and surjective. Guarantees a perfect pairing between domain and
codomain elements.