Sample Solution

IGNOU MMTE-001 Solved Assignment | 1st January, 2025 to 31st December, 2025 | GRAPH THEORY | MSc MACS Sample Solution

MMTE-001 Solved Assignment 2025

State whether the following statements are true or false. Justify your answers with a short proof or a counterexample
i) There exists an 8 -vertex graph with three vertices of degree 3 , four vertices of degree 2 and one vertex of degree 1.
ii) The neighbour of every leaf is a cut-vertex.
iii) Every line graph of a bipartite graph is 2-colourable.
iv) If $(d_{1}, d_{2}, \dots, d_{n})$ is a graphic sequence then so is $(d_{1} + 1, d_{2} + 1, \dots, d_{n} + 1)$ .
v) $β (K_{3} \times P_{3}) = 4$ .
vi) A Hamiltonian graph has no cut-vertices.
vii) The Petersen graph is 3-critical.
viii) An n-vertex star has no perfect matching for $n \geq 3$ .
ix) The crossing number of $K_{3, 3}$ is 2.
x) If f and g are two flows on a network N , then $max {f, g}$ is also a flow.
(a) If every cycle in a graph is even, then prove that the graph is bipartite. Is its converse true. Prove or disprove.

(b) For each n-vertex h-level complete binary tree, prove that

\log_{2} (n + 1) - 1 \leq h \leq \frac{n - 1}{2}

G

and

H

are isomorphic or not.

(a) Prove or disprove: A connected graph with order and size equal must contain exactly one cycle.

(b) Find a minimum-weight spanning tree in the following graph.

(d) Find the chromatic and edge-chromatic numbers of the following graph.

(a) Show that there are 14 spanning trees of the following graph. Draw all the spanning trees.

(b) Is it possible that a graph is 3 -chromatic but not 3 -critical? If so, explain it with an example.

(6, 5, 4, 4, 3, 1, 1, 1, 1)

is graphic or not. Also, find a graph realising it.

(a) Verify Euler’s formula for the following plane graph.

(b) Check whether the graph

C_{5} \times K_{5}

is planar or not.

G, κ^{'} (G) = κ (L (G))

. True or false? Justify.

(d) Find the matching number of the line graph of the graph given in part (a).
6. (a) What is the maximum possible flow that can pass through the following network

N

? Define such a flow.

(b) Show that

[S, T]

is an

(s, t)

-cut in network

N

give in part(a), where

S = {s, v_{1}, v_{2}, v_{3}}

and

T = {t, v_{4}, v_{5}, v_{6}}

. Also find

Cap (S, T)

. Does

N

have any other

(s, t)

-cut with capacity smaller than

Cap (S, T)

? What is the maximum possible value of a flow in N ?

(d) Provide an example of a 3-regular planar graph with 8-vertices. Is this graph a maximal planar graph? Why?

(a) Find the values of $n$ and $m$ for which the star graph $S_{n, m}$ is Eulerian.

(b) Using Fleury’s algorithm, find an Eulerian circuit in the following graph.

G

is a graph with

χ (G)

denoting its chromatic number, then

κ (G) \geq χ (G) - 1

(a) Find the line graph of the following graph? Write number of vertices and edges in the line graph.

(b) Find the thickness and crossing number of the graph

G

given in Q.2(c)?

C_{4} \times S_{4}

with explanation.

Answer:

Question:-1

State whether the following statements are true or false. Justify your answers with a short proof or a counterexample

i) There exists an 8-vertex graph with three vertices of degree 3, four vertices of degree 2 and one vertex of degree 1.

Answer:

We are asked whether there exists an 8-vertex graph with:

3 vertices of degree 3
4 vertices of degree 2
1 vertex of degree 1

Step 1: Degree Sum Check

Let’s apply the Handshaking Lemma, which says:

The sum of the degrees of all vertices in a graph is even, and equals 2 × number of edges.

Let’s compute the total degree sum:

(3 \times 3) + (4 \times 2) + (1 \times 1) = 9 + 8 + 1 = 18

This is even, so it’s possible in terms of degree sum.
Now we must check if a simple graph (no loops or multiple edges) can have such a degree sequence.

Step 2: Graphical Degree Sequence Check

Let’s consider the degree sequence (sorted in descending order):

[3, 3, 3, 2, 2, 2, 2, 1]

We can use the Havel-Hakimi algorithm to check if this degree sequence is graphical.

Havel-Hakimi Steps:

Sequence: [3, 3, 3, 2, 2, 2, 2, 1]
Take the first 3 → remove it → subtract 1 from next 3 degrees:

$[3, 3, 2, 2, 2, 1] \to b e c o m e s [2, 2, 1, 2, 1, 1]$

Sort: [2, 2, 2, 1, 1, 1]
Sequence: [2, 2, 2, 1, 1, 1]
Take 2 → remove it → subtract 1 from next 2:

$[2, 2, 1, 1, 1] \to b e c o m e s [1, 1, 1, 1, 1]$

Sorted: [1, 1, 1, 1, 1]
Sequence: [1, 1, 1, 1, 1]
Take 1 → remove it → subtract 1 from next 1:

$[1, 1, 1, 1] \to b e c o m e s [0, 1, 1, 1]$

Sorted: [1, 1, 1, 0]
Sequence: [1, 1, 1, 0]
Take 1 → remove it → subtract 1 from next 1:

[
[1, 1, 0] → becomes [0, 1, 0] → sort: [1, 0, 0]
Sequence: [1, 0, 0]
Take 1 → remove it → subtract 1 from next 1:

[
[0, 0] → done.

Conclusion

Yes, such a graph exists.

Degree sum is even ✔️
Degree sequence is graphical (passes Havel-Hakimi) ✔️

Answer: True.

There exists an 8-vertex graph with degrees 3, 3, 3, 2, 2, 2, 2, 1.

ii) The neighbour of every leaf is a cut-vertex.

Answer:

Statement: The neighbour of every leaf is a cut-vertex.

Answer: True.

Justification: In a graph, a leaf is a vertex with degree 1, meaning it has exactly one neighbor. Let

v

be a leaf and

u

be its neighbor. A cut-vertex is a vertex whose removal increases the number of connected components in the graph. If

u

is removed, the edge

u v

is also removed, leaving

v

isolated (since

v

has no other neighbors). This increases the number of connected components by at least 1 (as

v

becomes a separate component). Thus,

u

is a cut-vertex.

iii) Every line graph of a bipartite graph is 2-colourable.

Answer:

Statement: Every line graph of a bipartite graph is 2-colourable.

Answer: True.

Justification: A graph is 2-colourable if its vertices can be colored with two colors such that no adjacent vertices share the same color. For a bipartite graph

G = (A \cup B, E)

, its edges can be partitioned into those incident to vertices in

A

and those incident to vertices in

B

. The line graph

L (G)

has vertices corresponding to edges of

G

, with two vertices in

L (G)

adjacent if their corresponding edges in

G

share a common endpoint. Since

G

is bipartite, edges sharing an endpoint in

A

can be colored one color (say, color 1), and edges sharing an endpoint in

B

can be colored another color (say, color 2). This coloring ensures that adjacent vertices in

L (G)

(corresponding to edges sharing a vertex in

G

) have different colors, as one edge is incident to a vertex in

A

and the other to a vertex in

B

. Thus,

L (G)

is 2-colourable.

iv) If

(d_{1}, d_{2}, \dots, d_{n})

is a graphic sequence then so is

(d_{1} + 1, d_{2} + 1, \dots, d_{n} + 1)

Answer:

Statement: If $(d_{1}, d_{2}, \dots, d_{n})$ is a graphic sequence, then so is $(d_{1} + 1, d_{2} + 1, \dots, d_{n} + 1)$ .

Answer: False.

Justification: A sequence

(d_{1}, d_{2}, \dots, d_{n})

is graphic if there exists a simple graph with

n

vertices having degrees

d_{1}, d_{2}, \dots, d_{n}

. Consider the graphic sequence

(2, 2, 2, 2)

for

n = 4

, which corresponds to a simple graph like a cycle

C_{4}

(each vertex has degree 2). The sum of degrees is

2 + 2 + 2 + 2 = 8

, which is even, satisfying the Handshaking Lemma.

Now, consider the sequence

(d_{1} + 1, d_{2} + 1, d_{3} + 1, d_{4} + 1) = (3, 3, 3, 3)

. The sum of degrees is

3 + 3 + 3 + 3 = 12

, which is even. However, for a simple graph with 4 vertices, the maximum degree of a vertex is 3 (as a vertex can connect to at most 3 others). If all vertices have degree 3, the graph would be

K_{4}

(complete graph on 4 vertices), which has degree sequence

(3, 3, 3, 3)

. But we must check if increasing each degree by 1 preserves the graphic property in general.

A counterexample is the sequence

(1, 1, 1, 1)

for

n = 4

, which is graphic (e.g., a graph with two disjoint edges, like vertices

v_{1} - v_{2}

and

v_{3} - v_{4}

). The sum of degrees is

1 + 1 + 1 + 1 = 4

, which is even. Now consider

(1 + 1, 1 + 1, 1 + 1, 1 + 1) = (2, 2, 2, 2)

, which is graphic (as shown above, e.g.,

C_{4}

However, let’s try a sequence where the increase causes an issue. Take

(2, 2, 1, 1)

for

n = 4

, which is graphic (e.g., a path

v_{1} - v_{2} - v_{3}

with an isolated vertex

v_{4}

). The sum of degrees is

2 + 2 + 1 + 1 = 6

. Now consider

(2 + 1, 2 + 1, 1 + 1, 1 + 1) = (3, 3, 2, 2)

. The sum is

3 + 3 + 2 + 2 = 10

, which is even.

To check if

(3, 3, 2, 2)

is graphic, use the Havel-Hakimi theorem: sort the sequence (already sorted:

3, 3, 2, 2

), subtract 1 from the next 3 numbers (since the first degree is 3), and remove the first number:

(3 - 1, 2 - 1, 2 - 1) = (2, 1, 1)

. Sort again:

(2, 1, 1)

. Apply again: subtract 1 from the next 2 numbers:

(1 - 1, 1 - 1) = (0, 0)

. Since we obtain all zeros, the sequence

(3, 3, 2, 2)

is graphic.

Instead, consider a larger graph to find a clearer counterexample. Take

(3, 3, 3, 3, 3, 3)

for

n = 6

, which is graphic (e.g., a 3-regular graph like the Petersen graph or two disjoint triangles). The sum of degrees is

3 \times 6 = 18

. Now consider

(4, 4, 4, 4, 4, 4)

The sum is

4 \times 6 = 24

, which is even. For a simple graph with 6 vertices, the maximum degree is 5. A degree sequence where all vertices have degree 4 suggests a 4-regular graph. Apply Havel-Hakimi: take

(4, 4, 4, 4, 4, 4)

, remove the first 4, subtract 1 from the next 4 numbers:

(4 - 1, 4 - 1, 4 - 1, 4 - 1, 4) = (3, 3, 3, 3, 4)

. Sort:

(4, 3, 3, 3, 3)

Remove the first 4, subtract 1 from the next 4:

(3 - 1, 3 - 1, 3 - 1, 3 - 1) = (2, 2, 2, 2)

. Sort:

(2, 2, 2, 2)

. Remove the first 2, subtract 1 from the next 2:

(2 - 1, 2 - 1, 2) = (1, 1, 2)

. Sort:

(2, 1, 1)

. Remove the first 2, subtract 1 from the next 2:

(1 - 1, 1 - 1) = (0, 0)

. The sequence reduces to zeros, so

(4, 4, 4, 4, 4, 4)

is graphic.

The issue arises when the degree sum or constraints violate simplicity. Consider

(4, 4, 4, 4, 4, 4, 4)

for

n = 7

, which is graphic (e.g., a 4-regular graph exists). The sum is

4 \times 7 = 28

. Now take

(5, 5, 5, 5, 5, 5, 5)

The sum is

5 \times 7 = 35

, which is odd. By the Handshaking Lemma, the sum of degrees in a graph must be even (since each edge contributes 2 to the degree sum). Thus,

(5, 5, 5, 5, 5, 5, 5)

cannot be graphic, as its degree sum is odd, violating a necessary condition for a graph.

This counterexample shows the statement is false:

(4, 4, 4, 4, 4, 4, 4)

is graphic, but

(5, 5, 5, 5, 5, 5, 5)

is not.

β (K_{3} \times P_{3}) = 4

Answer:

Statement: $β (K_{3} \times P_{3}) = 4$ .

Answer: True.

Justification: The graph

K_{3} \times P_{3}

is the Cartesian product of a complete graph

K_{3}

(a triangle with 3 vertices) and a path graph

P_{3}

(3 vertices in a line, with 2 edges). The Cartesian product

G \times H

has vertex set

V (G) \times V (H)

, with vertices

(u, v)

and

(u^{'}, v^{'})

adjacent if either

u = u^{'}

and

v \sim v^{'}

H

, or

v = v^{'}

and

u \sim u^{'}

G

. Here,

K_{3}

has vertices

{a, b, c}

with edges

{a b, b c, c a}

, and

P_{3}

has vertices

{1, 2, 3}

with edges

{1 - 2, 2 - 3}

. Thus,

K_{3} \times P_{3}

has

3 \times 3 = 9

vertices, labeled as

(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)

Edges in

K_{3} \times P_{3}

are:

For fixed $u \in {a, b, c}$ , vertices $(u, i)$ and $(u, j)$ are adjacent if $i \sim j$ in $P_{3}$ . Since $P_{3}$ has edges $1 - 2$ and $2 - 3$ , we get edges like $(a, 1) - (a, 2)$ , $(a, 2) - (a, 3)$ , and similarly for $b$ and $c$ . This forms three copies of $P_{3}$ , one for each $u$ .
For fixed $v \in {1, 2, 3}$ , vertices $(u, v)$ and $(u^{'}, v)$ are adjacent if $u \sim u^{'}$ in $K_{3}$ . Since $K_{3}$ has edges $a b, b c, c a$ , for $v = 1$ , we get edges $(a, 1) - (b, 1)$ , $(b, 1) - (c, 1)$ , $(c, 1) - (a, 1)$ , forming a $K_{3}$ . Similarly for $v = 2$ and $v = 3$ .

Thus, the graph consists of three layers of

K_{3}

(at

v = 1, 2, 3

) connected by three

P_{3}

chains (along

u = a, b, c

). The graph resembles a triangular prism with an extra middle layer, sometimes called the grid graph

C_{3} ◻ P_{3}

The term

β (G)

typically denotes the vertex cover number, the size of the smallest set of vertices that covers all edges (i.e., every edge is incident to at least one vertex in the set). To find

β (K_{3} \times P_{3})

Lower bound: The graph has 9 vertices, and we need to cover all edges. The degree of each vertex can help estimate the minimum cover. In $K_{3} \times P_{3}$ , vertices like $(a, 2)$ have degree 4 (connected to $(a, 1)$ , $(a, 3)$ in the $P_{3}$ chain, and $(b, 2)$ , $(c, 2)$ in the $K_{3}$ layer), while corners like $(a, 1)$ have degree 3. A vertex cover must include at least one endpoint of each edge. Consider the edge set size: each $K_{3}$ layer has 3 edges (since $K_{3}$ has 3 edges), so three layers contribute $3 \times 3 = 9$ edges. Each $P_{3}$ chain has 2 edges, so three chains contribute $3 \times 2 = 6$ edges. Total edges = $9 + 6 = 15$ . A single vertex covers at most its degree number of edges (e.g., 4 for $(a, 2)$ ). Covering 15 edges with degree-4 vertices suggests at least $⌈ 15 / 4 ⌉ = 4$ vertices.
Attempt a vertex cover of size 4: Take vertices $(a, 1)$ $(a, 1)$ (a,1)(a,1) $(a, 1)$ , $(a, 2)$ $(a, 2)$ (a,2)(a,2) $(a, 2)$ , $(b, 2)$ $(b, 2)$ (b,2)(b,2) $(b, 2)$ , $(b, 3)$ $(b, 3)$ (b,3)(b,3) $(b, 3)$ . Check covered edges:
- For $u = a$ : $(a, 1) - (a, 2)$ , $(a, 2) - (a, 3)$ are covered (since $(a, 1)$ , $(a, 2)$ are included).
- For $u = b$ : $(b, 1) - (b, 2)$ , $(b, 2) - (b, 3)$ are covered (since $(b, 2)$ , $(b, 3)$ are included).
- For $u = c$ : $(c, 1) - (c, 2)$ , $(c, 2) - (c, 3)$ are not covered yet.
- For $v = 1$ : $(a, 1) - (b, 1)$ , $(b, 1) - (c, 1)$ , $(c, 1) - (a, 1)$ are covered by $(a, 1)$ , $(b, 1)$ , but we need $(c, 1)$ .
- For $v = 2$ : $(a, 2) - (b, 2)$ , $(b, 2) - (c, 2)$ , $(c, 2) - (a, 2)$ are covered by $(a, 2)$ , $(b, 2)$ .
- For $v = 3$ : $(a, 3) - (b, 3)$ , $(b, 3) - (c, 3)$ , $(c, 3) - (a, 3)$ are covered by $(b, 3)$ , but we need $(a, 3)$ , $(c, 3)$ .

Instead, try

(a, 1)

(b, 1)

(a, 3)

(b, 3)

$K_{3}$ at $v = 1$ : $(a, 1) - (b, 1)$ , $(b, 1) - (c, 1)$ , $(c, 1) - (a, 1)$ covered by $(a, 1)$ , $(b, 1)$ .
$K_{3}$ at $v = 3$ : $(a, 3) - (b, 3)$ , $(b, 3) - (c, 3)$ , $(c, 3) - (a, 3)$ covered by $(a, 3)$ , $(b, 3)$ .
$P_{3}$ for $u = a$ : $(a, 1) - (a, 2)$ , $(a, 2) - (a, 3)$ covered by $(a, 1)$ , $(a, 3)$ .
$P_{3}$ for $u = b$ : $(b, 1) - (b, 2)$ , $(b, 2) - (b, 3)$ covered by $(b, 1)$ , $(b, 3)$ .
$K_{3}$ at $v = 2$ : $(a, 2) - (b, 2)$ , $(b, 2) - (c, 2)$ , $(c, 2) - (a, 2)$ not covered yet.
$P_{3}$ for $u = c$ : $(c, 1) - (c, 2)$ , $(c, 2) - (c, 3)$ not covered.

Try a better set:

(a, 1)

(b, 1)

(b, 2)

(c, 3)

$v = 1$ : $(a, 1) - (b, 1)$ , $(b, 1) - (c, 1)$ , $(c, 1) - (a, 1)$ covered by $(a, 1)$ , $(b, 1)$ .
$v = 2$ : $(a, 2) - (b, 2)$ , $(b, 2) - (c, 2)$ , $(c, 2) - (a, 2)$ covered by $(b, 2)$ .
$v = 3$ : $(a, 3) - (b, 3)$ , $(b, 3) - (c, 3)$ , $(c, 3) - (a, 3)$ covered by $(c, 3)$ .
$u = a$ : $(a, 1) - (a, 2)$ , $(a, 2) - (a, 3)$ covered by $(a, 1)$ .
$u = b$ : $(b, 1) - (b, 2)$ , $(b, 2) - (b, 3)$ covered by $(b, 1)$ , $(b, 2)$ .
$u = c$ : $(c, 1) - (c, 2)$ , $(c, 2) - (c, 3)$ covered by $(c, 3)$ .

This set covers all 15 edges. To confirm minimality, a vertex cover of size 3 would cover at most

4 + 4 + 4 = 12

edges (assuming maximum degree 4), which is less than 15, so

β \geq 4

. Since we found a cover of size 4,

β (K_{3} \times P_{3}) = 4

vi) A Hamiltonian graph has no cut-vertices.

Answer:

Statement: A Hamiltonian graph has no cut-vertices.

Answer: True.

Justification: A Hamiltonian graph has a cycle that visits every vertex exactly once, called a Hamiltonian cycle. Suppose

G

is Hamiltonian with a Hamiltonian cycle

C = v_{1}, v_{2}, \dots, v_{n}, v_{1}

. A cut-vertex is a vertex whose removal increases the number of connected components. If any vertex

v_{i}

is removed, the remaining graph

G - v_{i}

still contains the path

v_{1}, v_{2}, \dots, v_{i - 1}, v_{i + 1}, \dots, v_{n}

, which connects all other vertices in a single component (since

C

spans all vertices). Thus, removing any vertex does not disconnect the graph, so

G

has no cut-vertices.

vii) The Petersen graph is 3-critical.

Answer:

Statement: The Petersen graph is 3-critical.

Answer: True.

Justification: A graph

G

k

-critical if its chromatic number

χ (G) = k

and removing any vertex reduces the chromatic number, i.e.,

χ (G - v) < k

for all vertices

v

. The Petersen graph has 10 vertices, is 3-regular, and is known to have chromatic number

χ (G) = 3

(it can be 3-colored, but not 2-colored, as it contains odd cycles like

C_{5}

To verify if it is 3-critical:

Remove any vertex $v$ and its 3 edges. The resulting graph $G - v$ has 9 vertices and is no longer 3-regular (neighbors of $v$ now have degree 2). The Petersen graph’s structure includes $C_{5}$ cycles and is highly symmetric. Consider its outer 5-cycle and inner star-like structure connected by edges. Removing one vertex disrupts this, often leaving a graph with a 2-colorable structure. For example, $G - v$ can be shown to be bipartite in some cases (e.g., it may resemble a graph with an even cycle like $C_{6}$ or $C_{8}$ after edge adjustments), implying $χ (G - v) \leq 2$ .
A key property of the Petersen graph is that any subgraph obtained by removing a vertex has a chromatic number of 2. This is because $G - v$ often contains no odd cycles of length 3 (since the Petersen graph is triangle-free) and can be partitioned into two independent sets due to its structure.

Since

χ (G) = 3

and

χ (G - v) = 2 < 3

for any vertex

v

, the Petersen graph is 3-critical.

viii) An n-vertex star has no perfect matching for

n \geq 3

Answer:

To determine whether the statement "An n-vertex star has no perfect matching for

n \geq 3

" is true, let’s analyze it step-by-step with a clear and concise justification.

A star graph with

n

vertices, often denoted

S_{n}

K_{1, n - 1}

, consists of one central vertex connected to

n - 1

leaf vertices, with no edges between the leaves. For example:

For $n = 3$ , the star has one center vertex and two leaf vertices (like a path $v_{1} - v_{2} - v_{3}$ , where $v_{2}$ is the center).
For $n = 4$ , it has one center vertex and three leaf vertices, and so on.

A perfect matching in a graph is a set of edges such that every vertex in the graph is incident to exactly one edge in the matching. For a graph with

n

vertices to have a perfect matching:

$n$ must be even (since each edge covers two vertices).
The edges must pair up all vertices exactly.

Now, let’s evaluate the statement: "An n-vertex star has no perfect matching for

n \geq 3

Step 1: Understand the condition $n \geq 3$

The statement applies to star graphs with at least 3 vertices. We need to check if such graphs have perfect matchings, considering whether

n

is even or odd, since perfect matchings require an even number of vertices.

Step 2: Analyze the star graph structure

In an n-vertex star:

There is one central vertex, say $v_{c}$ , with degree $n - 1$ (connected to all $n - 1$ leaf vertices).
There are $n - 1$ leaf vertices, each with degree 1 (connected only to $v_{c}$ ).
The total number of edges is $n - 1$ , since each leaf is connected to the center by one edge.

Step 3: Perfect matching requirements

For a perfect matching:

Each of the $n$ vertices (the center and $n - 1$ leaves) must be matched exactly once.
Since each edge in the matching covers two vertices, a perfect matching requires $n / 2$ edges.
Only edges in the graph can be used, so in a star, these must be edges between the center and the leaves.

Step 4: Case analysis based on $n$

Let’s consider the parity of

n

, as perfect matchings are only possible when

n

is even.

Case 1: $n$ is odd ( $n \geq 3$ )

Examples:

n = 3, 5, 7, \dots

If $n$ is odd, a perfect matching is impossible because $n$ is not divisible by 2.
For instance:
- $n = 3$ : The star has 3 vertices (1 center, 2 leaves). A perfect matching would need $3 / 2 = 1.5$ edges, which is not an integer. Alternatively, with 3 vertices, we can’t pair all vertices into edges (one vertex would be left unmatched).
- $n = 5$ : 1 center, 4 leaves. We’d need $5 / 2 = 2.5$ edges, which is impossible.
Conclusion for odd $n$ : No perfect matching exists because $n$ is odd, violating the basic requirement for a perfect matching.

Case 2: $n$ is even ( $n \geq 4$ )

Examples:

n = 4, 6, 8, \dots

Now $n$ is even, so a perfect matching would have $n / 2$ edges, covering all $n$ vertices.
Let’s try to construct a perfect matching:
- $n = 4$ : 1 center, 3 leaves ( $v_{1}, v_{2}, v_{3}$ $v_{1}, v_{2}, v_{3}$ v_(1),v_(2),v_(3)v_1, v_2, v_3 $v_{1}, v_{2}, v_{3}$ , with center $v_{c}$ $v_{c}$ v_(c)v_c $v_{c}$ ).
  - Edges: $v_{c} - v_{1}, v_{c} - v_{2}, v_{c} - v_{3}$ .
  - A perfect matching needs $4 / 2 = 2$ edges, covering all 4 vertices.
  - Suppose we pick edge $v_{c} - v_{1}$ $v_{c} - v_{1}$ v_(c)-v_(1)v_c – v_1 $v_{c} - v_{1}$ :
    - This matches $v_{c}$ and $v_{1}$ .
    - Remaining vertices: $v_{2}, v_{3}$ .
    - There is no edge between $v_{2}$ and $v_{3}$ (leaves are not connected).
  - Try another edge, say $v_{c} - v_{2}$ $v_{c} - v_{2}$ v_(c)-v_(2)v_c – v_2 $v_{c} - v_{2}$ :
    - Matches $v_{c}, v_{2}$ .
    - Remaining: $v_{1}, v_{3}$ , no edge between them.
  - The center $v_{c}$ can only be matched to one leaf, using up its degree (since it’s in exactly one edge in the matching).
  - After picking one edge (e.g., $v_{c} - v_{1}$ ), the remaining $n - 2 = 2$ leaves (e.g., $v_{2}, v_{3}$ ) need to be matched, but they have no edges between them.
  - Thus, we can’t form a second edge for the matching.
- $n = 6$ : 1 center, 5 leaves.
  - Need $6 / 2 = 3$ edges.
  - Pick $v_{c} - v_{1}$ : covers $v_{c}, v_{1}$ .
  - Remaining: 4 leaves, needing 2 more edges.
  - No edges exist among the leaves, so we can’t continue the matching.
Generalize for even $n$ :
- Choose an edge $v_{c} - v_{i}$ , covering the center and one leaf.
- Remaining: $n - 2$ vertices (all leaves).
- A perfect matching for these requires $(n - 2) / 2$ edges.
- Since leaves have no edges between them, no further edges can be added.
- The maximum number of edges in a matching is 1 (covering the center and one leaf), which gives $| M | = 1$ , covering 2 vertices.
- For a perfect matching, we need $| M | = n / 2$ . Since $n \geq 4$ , $n / 2 \geq 2$ , but the matching number (maximum matching size) is at most 1, which is less than $n / 2$ .

Step 5: Evaluate the statement

The statement claims there is no perfect matching for

n \geq 3

Odd $n$ : True, because $n$ is not even, so no perfect matching is possible in any graph.
Even $n$ : True, because in a star graph, after matching the center to one leaf, the remaining $n - 2$ leaves cannot be paired due to the lack of edges between them.

Step 6: Consider edge cases

$n = 3$ : Already covered (odd, no perfect matching).
$n = 2$ : Not covered by $n \geq 3$ $n \geq 3$ n >= 3n \geq 3 $n \geq 3$ , but let’s check for completeness:
- Star with 2 vertices: $K_{2}$ , one edge.
- Perfect matching exists (use the edge).
- This doesn’t affect the statement since $n = 2$ is excluded.

Step 7: Conclusion

The statement is true for all

n \geq 3

Proof:
- If $n$ is odd, no graph with $n$ vertices has a perfect matching, as $n$ is not even.
- If $n$ is even ( $n \geq 4$ ), the star graph $S_{n}$ has one center and $n - 1$ leaves. A perfect matching requires $n / 2 \geq 2$ edges, but any matching can include at most one edge (center to one leaf), leaving $n - 2 \geq 2$ unmatched leaves with no edges between them, making a perfect matching impossible.

Final Answer

The statement is true.
Justification: For

n \geq 3

, an n-vertex star has no perfect matching. If

n

is odd, no perfect matching exists since

n

is not even. If

n

is even (

n \geq 4

), a matching can include at most one edge (center to a leaf), covering 2 vertices, but a perfect matching requires

n / 2 \geq 2

edges to cover all

n

vertices, which is impossible since the remaining

n - 2

leaves have no edges between them.

ix) The crossing number of

K_{3, 3}

is 2.

Answer:

To determine whether the statement "The crossing number of

K_{3, 3}

is 2" is true, let’s analyze it with a concise justification.

The crossing number of a graph

G

, denoted

c r (G)

, is the minimum number of edge crossings in any drawing of

G

in the plane.

K_{3, 3}

is a complete bipartite graph with two sets of 3 vertices each, where every vertex in one set is connected to every vertex in the other set, resulting in

3 \times 3 = 9

edges.

Step 1: Known results about $K_{3, 3}$

K_{3, 3}

is a well-studied graph in graph theory:

It is non-planar, meaning it cannot be drawn in the plane without any edge crossings (i.e., $c r (K_{3, 3}) \geq 1$ ).
A classic result states that the crossing number of $K_{3, 3}$ is exactly 1. This can be shown by constructing a drawing with one crossing and proving that no drawing with zero crossings (planar) is possible.

Step 2: Evaluate the statement

The statement claims

c r (K_{3, 3}) = 2

. Let’s test this:

Is $c r (K_{3, 3}) \leq 1$ possible?
- There exists a standard drawing of $K_{3, 3}$ $K_{3, 3}$ K_(3,3)K_{3,3} $K_{3, 3}$ with one crossing. For example:
  - Place three vertices $A_{1}, A_{2}, A_{3}$ on one side of a line and $B_{1}, B_{2}, B_{3}$ on the other.
  - Draw edges such that most are straight, but one pair of edges (e.g., $A_{1} - B_{2}$ and $A_{2} - B_{1}$ ) crosses once.
  - This drawing has exactly one crossing point.
- Thus, $c r (K_{3, 3}) \leq 1$ .
Is $c r (K_{3, 3}) = 0$ possible?
- $K_{3, 3}$ is one of Kuratowski’s graphs and is non-planar by Kuratowski’s theorem.
- Alternatively, Wagner’s theorem implies that a graph is planar if it has no $K_{5}$ or $K_{3, 3}$ minor. Since $K_{3, 3}$ contains itself as a subgraph (or minor), it is not planar.
- Thus, $c r (K_{3, 3}) \geq 1$ .
Conclusion from bounds:
- Since $c r (K_{3, 3}) \leq 1$ and $c r (K_{3, 3}) \geq 1$ , it follows that $c r (K_{3, 3}) = 1$ .
Compare with the statement:
- The statement claims $c r (K_{3, 3}) = 2$ , but we’ve established $c r (K_{3, 3}) = 1$ .
- Therefore, the statement is false.

Step 3: Provide a counterexample

A counterexample to the statement is the drawing of

K_{3, 3}

with only one crossing (as described above), which shows that the crossing number is at most 1, not 2.

Final Answer

The statement is false.
Justification: The crossing number of

K_{3, 3}

is 1, not 2, because

K_{3, 3}

can be drawn in the plane with exactly one edge crossing, and it is non-planar, requiring at least one crossing. A drawing with vertices split into two sets of three and edges arranged to cross once demonstrates this.

x) If f and g are two flows on a network N, then

max {f, g}

is also a flow.

Answer:

To determine whether the statement "If

f

and

g

are two flows on a network

N

, then

max {f, g}

is also a flow" is true, let’s analyze it with a concise justification.

A network

N = (G, s, t, c)

consists of a directed graph

G = (V, E)

, a source vertex

s

, a sink vertex

t

, and a capacity function

c : E \to R_{\geq 0}

. A flow

f : E \to R_{\geq 0}

N

satisfies:

Capacity constraint: For each edge $e \in E$ , $0 \leq f (e) \leq c (e)$ .
Flow conservation: For each vertex $v \in V ∖ {s, t}$ , the sum of flows into $v$ equals the sum of flows out of $v$ : $\sum_{e into v} f (e) = \sum_{e out of v} f (e) .$

The statement defines

max {f, g}

for two flows

f

and

g

, which we interpret as the function

h : E \to R_{\geq 0}

where

h (e) = max {f (e), g (e)}

for each edge

e

. We need to check if

h

is a flow, i.e., if it satisfies both the capacity constraint and flow conservation.

Step 1: Check the capacity constraint

Since $f$ $f$ ff $f$ and $g$ $g$ gg $g$ are flows, for each edge $e$ $e$ ee $e$ :
- $0 \leq f (e) \leq c (e)$ ,
- $0 \leq g (e) \leq c (e)$ .
Thus, $h (e) = max {f (e), g (e)} \leq c (e)$ , because both $f (e) \leq c (e)$ and $g (e) \leq c (e)$ .
Also, $h (e) \geq 0$ , since $f (e) \geq 0$ and $g (e) \geq 0$ .
Therefore, $h$ satisfies the capacity constraint: $0 \leq h (e) \leq c (e)$ .

Step 2: Check flow conservation

For $h$ to be a flow, at each vertex $v \in V ∖ {s, t}$ , the total flow in must equal the total flow out: $\sum_{e into v} h (e) = \sum_{e out of v} h (e) .$
Since $f$ and $g$ are flows, they satisfy conservation at $v$ : $\sum_{e into v} f (e) = \sum_{e out of v} f (e), \sum_{e into v} g (e) = \sum_{e out of v} g (e) .$
However, $h (e) = max {f (e), g (e)}$ assigns flow to each edge independently, which may disrupt conservation. Let’s test with an example.

Step 3: Construct a counterexample

Consider a simple network:

Vertices: ${s, u, t}$ .
Edges: $(s, u)$ , $(u, t)$ .
Capacities: $c (s, u) = 1$ , $c (u, t) = 1$ .
Source $s$ , sink $t$ .

Define two flows:

Flow $f$ $f$ ff $f$ :
- $f (s, u) = 1$ ,
- $f (u, t) = 1$ .
- Conservation at $u$ : Inflow $f (s, u) = 1$ , outflow $f (u, t) = 1$ . Satisfied.
- Capacity: $f (s, u) = 1 \leq 1$ , $f (u, t) = 1 \leq 1$ . Satisfied.
Flow $g$ $g$ gg $g$ :
- $g (s, u) = 0$ ,
- $g (u, t) = 0$ .
- Conservation at $u$ : Inflow $g (s, u) = 0$ , outflow $g (u, t) = 0$ . Satisfied.
- Capacity: $g (s, u) = 0 \leq 1$ , $g (u, t) = 0 \leq 1$ . Satisfied.

Now compute

h = max {f, g}

$h (s, u) = max {f (s, u), g (s, u)} = max {1, 0} = 1$ .
$h (u, t) = max {f (u, t), g (u, t)} = max {1, 0} = 1$ .

Check conservation at

u

Inflow: $h (s, u) = 1$ .
Outflow: $h (u, t) = 1$ .
$1 = 1$ , so conservation holds here.

This example seems to work, so let’s try a more complex network to expose potential issues:

Vertices: ${s, u, v, t}$ .
Edges: $(s, u)$ , $(s, v)$ , $(u, v)$ , $(u, t)$ , $(v, t)$ .
Capacities: $c (e) = 1$ for all edges.

Define two flows:

Flow $f$ $f$ ff $f$ :
- $f (s, u) = 1$ , $f (u, v) = 1$ , $f (v, t) = 1$ .
- $f (s, v) = 0$ , $f (u, t) = 0$ .
- Check conservation:
  - At $u$ : Inflow $f (s, u) = 1$ ; outflow $f (u, v) + f (u, t) = 1 + 0 = 1$ . Satisfied.
  - At $v$ : Inflow $f (s, v) + f (u, v) = 0 + 1 = 1$ ; outflow $f (v, t) = 1$ . Satisfied.
- Capacity: All values are 0 or 1, satisfying $f (e) \leq 1$ .
Flow $g$ $g$ gg $g$ :
- $g (s, v) = 1$ , $g (v, t) = 1$ .
- $g (s, u) = 0$ , $g (u, v) = 0$ , $g (u, t) = 0$ .
- Check conservation:
  - At $u$ : Inflow $g (s, u) = 0$ ; outflow $g (u, v) + g (u, t) = 0 + 0 = 0$ . Satisfied.
  - At $v$ : Inflow $g (s, v) + g (u, v) = 1 + 0 = 1$ ; outflow $g (v, t) = 1$ . Satisfied.
- Capacity: Satisfied.

Compute

h = max {f, g}

$h (s, u) = max {1, 0} = 1$ .
$h (s, v) = max {0, 1} = 1$ .
$h (u, v) = max {1, 0} = 1$ .
$h (u, t) = max {0, 0} = 0$ .
$h (v, t) = max {1, 1} = 1$ .

Check conservation at

u

Inflow: $h (s, u) = 1$ .
Outflow: $h (u, v) + h (u, t) = 1 + 0 = 1$ .
Satisfied.

Check conservation at

v

Inflow: $h (s, v) + h (u, v) = 1 + 1 = 2$ .
Outflow: $h (v, t) = 1$ .
$2 \neq 1$ , so flow conservation is violated.

Check capacity:

All $h (e) = 0$ or $1 \leq c (e) = 1$ , so capacity is satisfied.

Since

h

violates flow conservation at vertex

v

h = max {f, g}

is not a flow.

Step 4: Conclusion

The statement is false, as shown by the counterexample where

max {f, g}

satisfies capacity constraints but fails flow conservation.

Final Answer

The statement is false.
Justification: For flows

f

and

g

on a network,

max {f, g}

, defined edge-wise as

max {f (e), g (e)}

, may not satisfy flow conservation. In a network with vertices

s, u, v, t

and edges

(s, u), (s, v), (u, v), (u, t), (v, t)

, flows

f

(path

s \to u \to v \to t

) and

g

(path

s \to v \to t

) yield

max {f, g}

, which has inflow 2 and outflow 1 at

v

, violating conservation.

Question:-2(a)

If every cycle in a graph is even, then prove that the graph is bipartite. Is its converse true. Prove or disprove.

Answer:

To address the query, we need to prove that if every cycle in a graph is even, then the graph is bipartite, and then determine whether the converse is true by proving or disproving it.

Part 1: Prove that if every cycle in a graph is even, then the graph is bipartite.

A graph is bipartite if its vertex set can be partitioned into two disjoint sets

A

and

B

such that every edge connects a vertex in

A

to a vertex in

B

. Equivalently, a graph is bipartite if it has no odd cycles, because an odd cycle cannot be colored with two colors without adjacent vertices sharing the same color.

Assumption: Every cycle in the graph

G = (V, E)

is even, meaning the length of every cycle (number of edges) is an even number. This implies there are no odd cycles in

G

Proof:

Connected Components: If $G$ is disconnected, we can consider each connected component separately. A graph is bipartite if and only if all its connected components are bipartite. Thus, without loss of generality, assume $G$ is connected.
Choose a Root Vertex: Pick an arbitrary vertex $v_{0} \in V$ . We will attempt to construct a bipartition by assigning vertices to two sets based on their distance from $v_{0}$ .
Breadth-First Search (BFS): Perform a BFS starting from $v_{0}$ . Define:
- Set $A$ as the vertices at even distance from $v_{0}$ (including $v_{0}$ , at distance 0).
- Set $B$ as the vertices at odd distance from $v_{0}$ .
  Formally:
- $A = {u \in V ∣ distance (v_{0}, u) is even}$ ,
- $B = {u \in V ∣ distance (v_{0}, u) is odd}$ .
Verify Bipartition:
- Disjoint Sets: By definition, a vertex $u$ has either an even or odd distance from $v_{0}$ , so $A \cap B = \emptyset$ . Since BFS reaches all vertices in a connected graph, $A \cup B = V$ .
- Edge Condition: We need to show every edge in $E$ $E$ EE $E$ connects a vertex in $A$ $A$ AA $A$ to a vertex in $B$ $B$ BB $B$ . Suppose there is an edge ${u, w}$ ${u, w}$ {u,w}\{u, w\} ${u, w}$ where both $u, w \in A$ $u, w \in A$ u,w in Au, w \in A $u, w \in A$ (or both in $B$ $B$ BB $B$ ). Since $u$ $u$ uu $u$ and $w$ $w$ ww $w$ are in $A$ $A$ AA $A$ , their distances from $v_{0}$ $v_{0}$ v_(0)v_0 $v_{0}$ , say $d (v_{0}, u) = 2 k$ $d (v_{0}, u) = 2 k$ d(v_(0),u)=2kd(v_0, u) = 2k $d (v_{0}, u) = 2 k$ and $d (v_{0}, w) = 2 m$ $d (v_{0}, w) = 2 m$ d(v_(0),w)=2md(v_0, w) = 2m $d (v_{0}, w) = 2 m$ , are even. Consider the following:
  - Take a shortest path $P_{1} : v_{0} \to u_{1} \to \dots \to u_{2 k} = u$ (length $2 k$ ).
  - Take a shortest path $P_{2} : v_{0} \to w_{1} \to \dots \to w_{2 m} = w$ (length $2 m$ ).
  - Since ${u, w} \in E$ , there is an edge from $u$ to $w$ .
  - Now, construct a cycle: Start at $v_{0}$ , follow $P_{1}$ to $u$ , take the edge ${u, w}$ to $w$ , and follow $P_{2}$ reversed back to $v_{0}$ (i.e., $w = w_{2 m} \to w_{2 m - 1} \to \dots \to v_{0}$ ).
  - Cycle Length: Compute the length of this cycle:
    - Path from $v_{0}$ to $u$ : $2 k$ edges.
    - Edge ${u, w}$ : 1 edge.
    - Path from $w$ back to $v_{0}$ : $2 m$ edges (since the reverse path has the same length).
    - Total length = $2 k + 1 + 2 m = 2 (k + m) + 1$ , which is odd.
  - This creates a cycle of odd length, contradicting the assumption that every cycle in $G$ is even.
  - Similarly, if $u, w \in B$ , their distances are odd, say $2 k + 1$ and $2 m + 1$ , and the cycle length becomes $(2 k + 1) + 1 + (2 m + 1) = 2 k + 2 m + 3 = 2 (k + m + 1) + 1$ , also odd, again a contradiction.
Conclusion: Since assuming an edge exists within $A$ or within $B$ leads to an odd cycle, no such edge can exist. Thus, every edge in $G$ connects a vertex in $A$ to a vertex in $B$ . Hence, $G$ is bipartite with bipartition $(A, B)$ .

Therefore, if every cycle in

G

is even,

G

is bipartite.

Part 2: Is the converse true? That is, if a graph is bipartite, does it follow that every cycle is even?

Converse Statement: If a graph

G

is bipartite, then every cycle in

G

is even.

Proof:

Bipartite Definition: Suppose $G = (V, E)$ is bipartite. Then, there exists a partition of $V$ into two disjoint sets $A$ and $B$ such that every edge in $E$ has one endpoint in $A$ and one in $B$ .
Cycle Analysis: Consider any cycle in $G$ : $v_{1} \to v_{2} \to \dots \to v_{k} \to v_{1}$ , where ${v_{i}, v_{i + 1}} \in E$ for $i = 1, \dots, k - 1$ , and ${v_{k}, v_{1}} \in E$ . The length of the cycle is $k$ .
Vertex Coloring: Since $G$ is bipartite, we can assign vertices to sets $A$ and $B$ . Without loss of generality, suppose $v_{1} \in A$ . Since ${v_{1}, v_{2}} \in E$ , $v_{2}$ must be in $B$ . Continuing:
- ${v_{2}, v_{3}} \in E$ , so $v_{3} \in A$ (since $v_{2} \in B$ ).
- ${v_{3}, v_{4}} \in E$ , so $v_{4} \in B$ .
- This alternates: vertices at odd positions ( $v_{1}, v_{3}, v_{5}, \dots$ ) are in $A$ , and vertices at even positions ( $v_{2}, v_{4}, v_{6}, \dots$ ) are in $B$ .
Closing the Cycle: For the cycle to close, $v_{k} \to v_{1}$ , the edge ${v_{k}, v_{1}}$ must exist. Since $v_{1} \in A$ , $v_{k} \in B$ . If the cycle has length $k$ :
- If $k$ is odd, say $k = 2 m + 1$ , the sequence is $v_{1} \in A, v_{2} \in B, v_{3} \in A, \dots, v_{2 m} \in B, v_{2 m + 1} \in A$ . Then, $v_{k} = v_{2 m + 1} \in A$ , but ${v_{k}, v_{1}}$ requires $v_{k} \in B$ , a contradiction since $v_{k}$ cannot be in both $A$ and $B$ .
- If $k$ is even, say $k = 2 m$ , the sequence is $v_{1} \in A, v_{2} \in B, \dots, v_{2 m - 1} \in A, v_{2 m} \in B$ . Then, $v_{k} = v_{2 m} \in B$ , and ${v_{k}, v_{1}}$ is valid since $v_{1} \in A$ , $v_{k} \in B$ .
Conclusion: An odd-length cycle is impossible in a bipartite graph because it violates the bipartition. Thus, every cycle in $G$ must have even length.

Therefore, the converse is true: if a graph is bipartite, every cycle is even.

Final Answer

First Part: If every cycle in a graph is even, the graph is bipartite (proven by constructing a bipartition using BFS and showing that edges within the same set imply an odd cycle, which contradicts the assumption).
Converse: The converse is true: if a graph is bipartite, every cycle is even (proven by showing that a bipartite graph’s structure forces cycles to alternate between two vertex sets, making odd cycles impossible).

The graph is bipartite if every cycle is even. The converse is true.

]

Back to Course

Next Lesson

IGNOU MMTE-001 Solved Assignment | 1st January, 2025 to 31st December, 2025 | GRAPH THEORY | MSc MACS

Sample Solution

MMTE-001 Solved Assignment 2025

Answer:

Question:-1

State whether the following statements are true or false. Justify your answers with a short proof or a counterexample

Answer:

Step 1: Degree Sum Check

Step 2: Graphical Degree Sequence Check

Havel-Hakimi Steps:

Conclusion

Answer: True.

Answer:

Answer:

Answer:

Answer:

Answer:

Answer:

Answer:

Step 1: Understand the condition n ≥ 3 n ≥ 3 n >= 3n \geq 3n≥3

Step 2: Analyze the star graph structure

Step 3: Perfect matching requirements

Step 4: Case analysis based on n n nnn

Case 1: n n nnn is odd ( n ≥ 3 n ≥ 3 n >= 3n \geq 3n≥3)

Case 2: n n nnn is even ( n ≥ 4 n ≥ 4 n >= 4n \geq 4n≥4)

Step 5: Evaluate the statement

Step 6: Consider edge cases

Step 7: Conclusion

Answer:

Step 1: Known results about K 3 , 3 K 3 , 3 K_(3,3)K_{3,3}K3,3

Step 2: Evaluate the statement

Step 3: Provide a counterexample

Final Answer

Answer:

Step 1: Check the capacity constraint

Step 2: Check flow conservation

Step 3: Construct a counterexample

Step 4: Conclusion

Question:-2(a)

If every cycle in a graph is even, then prove that the graph is bipartite. Is its converse true. Prove or disprove.

Answer:

Part 1: Prove that if every cycle in a graph is even, then the graph is bipartite.

Part 2: Is the converse true? That is, if a graph is bipartite, does it follow that every cycle is even?

Final Answer

Step 1: Understand the condition $n \geq 3$

Step 4: Case analysis based on $n$

Case 1: $n$ is odd ( $n \geq 3$ )

Case 2: $n$ is even ( $n \geq 4$ )

Step 1: Known results about $K_{3, 3}$