THEORY EXAMINATION (SEM–VI) 2016-17 GRAPH THEORY

GRAPH THEORY (ECS505)

SECTION – A

(Short Answer Questions | 2 Marks Each)

(a) Number of edges                                                Given: 16 vertices, each of degree 2
Using Handshaking Lemma:

∑deg⁡(v)=2∣E∣\sum \deg(v) = 2|E|∑deg(v)=2∣E∣ 16×2=2∣E∣⇒∣E∣=1616 \times 2 = 2|E| \Rightarrow |E| = 1616×2=2∣E∣⇒∣E∣=16

Number of edges = 16

(b) Bipartite graph (3 houses & 3 utilities)

This is a bipartite graph with partitions:                   Houses: H₁, H₂, H₃

Utilities: Water (W), Gas (G), Electricity (E)

Each house is connected to all three utilities, forming a complete bipartite graph K₃,₃.

(c) Rooted tree vs Binary tree

A rooted tree has a designated root vertex and a hierarchical structure.
A binary tree is a rooted tree where each node has at most two children.

(d) Thickness and Crossing Number

Thickness: Minimum number of planar subgraphs whose union is the given graph.

Crossing number: Minimum number of edge crossings in any planar drawing of the graph.

(e) Radius and Diameter

Eccentricity: Maximum distance from a vertex to any other vertex.

Radius: Minimum eccentricity among all vertices.

Diameter: Maximum eccentricity among all vertices.

(f) Matching

A matching is a set of edges with no common vertices.

(g) Chromatic number

The chromatic number (χ(G)) is the minimum number of colors needed to color the vertices so that no two adjacent vertices have the same color.
Example: χ(K₃) = 3.

(h) Hamiltonian but not Eulerian graph

A cycle with one extra chord is Hamiltonian (contains a Hamiltonian cycle) but not Eulerian (odd degree vertices exist).

(i) Fundamental circuits and cut-sets

Fundamental circuit: A cycle formed by adding one chord to a spanning tree.

Fundamental cut-set: A minimal set of edges whose removal disconnects the graph.

(j) Orthogonal vectors

Two vectors are orthogonal if their dot product is zero.

SECTION – B

(Descriptive Questions | 10 Marks Each)

(a) Edge connectivity & Vertex connectivity

Edge connectivity (λ): Minimum number of edges whose removal disconnects the graph.

Vertex connectivity (κ): Minimum number of vertices whose removal disconnects the graph.

A graph can be constructed with κ = 3, λ = 4, and minimum degree ≥ 3 by suitably modifying a complete graph and removing edges carefully.

(b) Incidence matrix, fundamental circuit & cut-set matrices

Incidence matrix: Rows represent vertices, columns represent edges.

Fundamental circuit matrix: Rows represent circuits formed by adding chords.

Fundamental cut-set matrix: Rows represent cut-sets formed by removing branches.

Relation:

Bf⋅CfT=0B_f \cdot C_f^T = 0Bf​⋅CfT​=0

They are orthogonal matrices.

(c) Minimum Spanning Tree (Prim’s Algorithm)

A minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

Using Prim’s algorithm on the given weighted graph, edges are selected with minimum weights without forming cycles until all vertices are connected.

Kuratowski’s Theorem:
A graph is planar if and only if it contains no subgraph homeomorphic to K₅ or K₃,₃.

(d) Maximum number of edges

For a simple graph with n vertices and k components:

∣E∣≤(n−k)(n−k+1)2|E| \le \frac{(n-k)(n-k+1)}{2}∣E∣≤2(n−k)(n−k+1)​

This is proved by considering each component as a complete graph.

(e)

(i) Konigsberg Bridge Problem:
Euler showed no Euler path exists because more than two vertices have odd degree.

(ii) Travelling Salesman Problem (TSP):
Find the shortest possible route that visits each city exactly once and returns to the origin.

(f) Chromatic polynomial

The chromatic polynomial P(G, λ) gives the number of ways to color a graph using λ colors.
It is obtained using deletion–contraction method.

(g) Max-Flow Min-Cut Theorem

The maximum flow in a network equals the minimum capacity of an s-t cut.
Verification is done by calculating flow values and identifying minimum cut.

SECTION – C

(Long Answer Questions | 15 Marks Each)

3(a) Edges in complete bipartite graph

For Kₘ,ₙ, each of m vertices connects to n vertices.

∣E∣=m×n|E| = m \times n∣E∣=m×n 

3(b) Pendant vertices in a binary tree

In a binary tree with n vertices, number of pendant (leaf) vertices is:

n+12\frac{n+1}{2}2n+1​

This is proved using degree sum property of trees.

3(c) Thickness and crossing number of Petersen graph

Thickness: 2

Crossing number: 2

4(a) Circuit and cut-set subspaces

Circuit subspace consists of all cycles.
Cut-set subspace consists of all minimal edge cuts.
Both are vector spaces over GF(2).

4(b) Incidence matrix rank

The rank of the incidence matrix of a connected graph with n vertices is (n − 1).
This is proved using linear dependence of rows.

4(c) Distance and eccentricity

Distance: Shortest path between two vertices.

Eccentricity: Maximum distance from a vertex to any other vertex.

Distance between spanning trees satisfies positivity, symmetry, and triangle inequality, hence is a metric.

5(a) Graph operations

Union: Combine vertex and edge sets

Intersection: Common vertices and edges

Ring sum: Edges present in exactly one graph

5(b) Fundamental cut-sets of K₅

Each branch of a spanning tree of K₅ generates a fundamental cut-set. All such cut-sets can be listed by removing one branch at a time.

5(c) Covering number and diameter

The covering number is related to the diameter such that a graph with small diameter generally has a larger covering number due to closer vertex proximity.