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?
(a) What is the maximum possible flow that can pass through the following network N? Define such a flow
(d) Find the matching number of the line graph of the graph given in part(a).
See Answer →(c) For every graph True or false? Justify.
(b) Check whether the graph is planar or not.
(c) Check the sequence (6, 5, 4, 4, 3, 1, 1, 1, 1) is graphic or not. Also, find a graph realising it.
See Answer →Is it possible that a graph is 3-chromatic but not 3-critical? If so, explain it with an example.
See Answer →(a) Show that there are 14 spanning trees of the following graph. Draw all the spanning trees.
(c) Determine the number of non-planar graphs with 6 vertices.
See Answer →
(a) Prove or disprove: A connected graph with order and size equal must contain exactly one cycle.
See Answer →
(a) Prove or disprove: A connected graph with order and size equal must contain exactly one cycle.
See Answer →(b) For each n-vertex h-level complete binary tree, prove that
2. (a) If every cycle in a graph is even, then prove that the graph is bipartite. Is its converse true. Prove or disprove.
See Answer →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 K3,3 is 2.
x) If f and g are two flows on a network N, then max is also a flow.
सोमदेव सूरि अथवा महात्मा गांधी
See Answer →