IGNOU MMTE 1 SOLVED ASSIGNMENT

Included:

MMTE 001 (January 2025 - July 2025) - ENGLISH

Assignment

(To be done after reading the course material)

Course Code: MMTE-001

Assignment Code: MMTE-001/TΜΑ/2025

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

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) is a graphic sequence then so is 

v)

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 ≥ 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 is also a flow.

2. (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  

(c) Check whether the following graphs G and H are isomorphic or not.

3. (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.

(c) Determine the number of non-planar graphs with 6 vertices. 

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

4. (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.

(c) Check the sequence (6, 5, 4, 4, 3, 1, 1, 1, 1) is graphic or not. Also, find a graph realising it.

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

(b) Check whether the graph is planar or not.

(c) For every graph 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 Does N have an other (s, t)-cut with capacity smaller than Cap(S, T)? What is the maximum possible value of a flow in N?

(c) State and prove Hall’s Theorem

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

7. (a) Find the values of n and m for which the star graph S_n,mis Eulerian.

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

(c) Prove or disprove: If G is a graph with χ(G) denoting its chromatic number, then

 

8. (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) Drawwith explanation.

Q: How will I receive the PDF?
A: Immediately after payment, the download link will appear and be sent to your email.

Q: Is this hand-written or typed?
A: This is a professional typed computer PDF. You can use it as a reference for your handwritten submission.