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 any connected graph with $\ge3$ vertices the neighbour of a leaf is a cut-vertex, but the statement as written for all graphs is false.) iii) False. Counterexample: take the star $K_{1,3}$ (which is _____ _______ __________ __________ ______.
______ _________ ____ ___ ______ ____ _______ ___ _________ _________ __________.
________ ____ ______ ______ __________ ____ ________ _______.
______ ____ ________ ___ ________ ________ _________.
_______ _________ _____ __________ __________ _______ ______ _________ ______ ______ __________.
___ ________ ___ _________ ______ __________ ____ _________.
______ ________ __________ ________ __________ __________.
__________ _______ _____ ______ ________ _____ _____ _________ ___ __________ ________.
____ _________ _________ ________ ________ ______ ___ ____ ____ __________ ______.
____ _________ ____ _______ ____ __________.
_________ ________ _____ _________ _______ ______ _______ ___ _______ _____ _________ _______.
________ _______ ________ ______ ______ ______ ______.
______ _____ _____ ____ ____ _____ ____ _______ __________ ________ __________ __________.
___ ______ __________ _______ ________ ______ _________ ___ ________ ____.
________ __________ _____ __________ ____ _______ ___ ___ __________ ________.
_______ ______ _______ ___ ___.
____ _______ _______ __________ _____ __________ _______ ____ _________ _____ _____.
__________ ________ ______ ___ __________ _________ _________ ___ ___ _______ ___.
______ ________ _____ _______ _____.
_________ ____ ______ __________ _____ ___.
____ _________ ______ _______ ____ ______ _______ ________.
_________ _________ ________ _____ ___ _______ _____ ________ _____ ____ _______ ____.
______ ______ ______ ____ ___ _________ _____ ______ ___ __________.
___ _______ ________ ___ _____ ___ _________ ______.
___ _____ ____ _______ ______.
________ _________ ___ _____ ____ _______ _________ _______ _______ _____.
____ ___ ________ _______ __________ ___ _________ _________.
_____ __________ __________ _______ ______ _________ ______ ______.
_________ _____ ________ __________ ___.
______ ________ ________ ____ _________ _________ ______ ____.
____ ______ ___ _______ _______.
_______ ________ ___ ______ __________ ___ ________ ____ _________.
______ __________ _______ ____ _______ ____ __________ ______ ___ ___.
______ __________ __________ _________ ____ ___ ________ _______.
____ _________ __________ _____.
Get Full Answer on WhatsApp
(c) Check the sequence (6, 5, 4, 4, 3, 1, 1, 1, 1) is graphic or not. Also, find a graph realising it.
(a) What is the maximum possible flow that can pass through the following network N? Define such a flow
Find the thickness and crossing number of the graph G given in Q.2(c)?
(a) Find the line graph of the following graph? Write number of vertices and edges in the line graph.
(d) Find the chromatic and edge-chromatic numbers of the following graph
Is it possible that a graph is 3-chromatic but not 3-critical? If so, explain it with an example.
Check whether the following graphs G and H are isomorphic or not.
