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.
i) True. Degrees: $3,3,3,2,2,2,2,1$ sum to $18$ (even) and Havel–Hakimi succeeds: $[3,3,3,2,2,2,2,1]\to[2,2,2,2,1,1]\to[2,1,1,1,1]\to[1,1,0,0]\to[0,0,0,0]$. Hence the sequence is graphic, so such an 8-vertex graph exists. ii) False. Counterexample: $K_2$ (two vertices joined by an edge). Each vertex is a leaf and the neighbour of a leaf is the other vertex; removing that neighbour leaves one vertex (still one component), so it is not a cut-vertex. (In __________ ____ _____ _________ ________ __________ ___ ___.
_________ __________ __________ ____ ________ ____ ________.
__________ _______ ___ _________ ________ ___ ____ _________ __________ __________.
_____ ___ _______ ______ _________ ____ ________.
________ ____ ______ _________ ______.
_________ _____ ______ ___ _________ _________ ____ ____ ________ ______.
__________ __________ __________ __________ _________ ___.
__________ _____ _____ _________ _____ _______ _________ ________ ______ ______ _______ ____.
_________ ______ _____ __________ ________ ____ ____ _________ ______ _________ _________ _____.
_____ __________ _______ ___ ____ _____ ____.
___ ____ ______ __________ ____ _____.
__________ __________ _______ ___ __________ ______ ___.
__________ _____ _______ _____ _________ ____ _______ ___ ____ _______.
____ ______ ___ _____ _______.
______ _____ __________ _____ ___.
__________ ____ ___ _____ _____ __________ ____ ___ _________ _______ ___ ______.
___ ________ _______ _______ ___ ___ _________ ________ _______ __________ ____.
_______ _________ ________ _____ ______.
___ ____ _______ _______ ___ _____ __________ _________.
_________ _______ ____ ____ _________ ________ ________ ____ _________.
______ _________ _______ _________ _____ ____ ___ _____.
_____ _____ ___ _________ ____ _______ _______.
_________ _______ ____ _________ ___ ________.
____ __________ _______ _______ ________ _________ ______ ________ _____.
______ ____ ___ ___ _________ ______ _____ __________.
________ ___ ___ ________ ____ ______ ___ _________ ________.
_____ _____ _____ ______ ____ _______ _________ _________ ___ _________ _____ ________.
_________ ___ _____ _______ _______ ____ _____ ___ _________ ____ _________ _____.
__________ ___ _____ ________ _________ _____ ___ _________.
____ ____ ___ __________ ____ ____ ________.
_______ ______ ________ _______ _________ _____.
_______ _______ ________ ________ ______ ________ __________ _____.
_______ ________ ______ _________ ___ _________ _______ ___ __________ ____ _____.
_____ _____ __________ ______ _____ _________ ______ _____ ___ _____ _______ ________.
___ ________ _________ _________ __________ ___ ___ ________ _________ ______ ___ _______.
________ __________ _____ ________ _______ ______ _____.
______ ___ _______ ___ ________ __________ _______ _______ _____.
____ _____ __________ __________ _____ __________ __________ __________ _________ ____.
_________.
Get Full Answer on WhatsApp
(d) Find the matching number of the line graph of the graph given in part(a).
(c) Check the sequence (6, 5, 4, 4, 3, 1, 1, 1, 1) is graphic or not. Also, find a graph realising it.
(a) Show that there are 14 spanning trees of the following graph. Draw all the spanning trees.
(a) Prove or disprove: A connected graph with order and size equal must contain exactly one cycle.
(c) State and prove Hall’s Theorem
(a) Prove or disprove: A connected graph with order and size equal must contain exactly one cycle.
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?