Q1. State whether the following statements are true or false. Justify your answers with a short proof or a counterexample.
- (i)) There exists a simple graph on 10 vertices with degree sequence (4,4,3,3,3,2,2,1,1,1). (80 words)
- (ii)) Every minimal vertex cut of a 2-connected graph induces a connected subgraph. (80 words)
- (iii)) If G is a connected graph with diameter 2, then χ(G) ≤ ∆(G) + 1. (80 words)
- (iv)) Every bipartite graph is planar. (80 words)
- (v)) Every 4-regular bipartite graph admits a proper 2-edge-colouring. (80 words)
- (vi)) Every graph is isomorphic to its complement. (80 words)
- (vii)) The Petersen graph is non-Hamiltonian. (80 words)
- (viii)) There exists a triangle-free graph G with χ(G) ≥ 4. (80 words)
- (ix)) For every integer k ≥ 4, any k-critical graph G satisfies |E(G)| ≥ (k−1)|V (G)|/2. (80 words)
- (x)) The hypercube Qn contains a Hamiltonian cycle for all n ≥ 2. (80 words)
Key Points:
- Havel-Hakimi theorem determines if a degree sequence is graphic.
- A minimal vertex cut in a 2-connected graph does not always induce a connected subgraph (e.g., C4).
- Brooks' Theorem establishes χ(G) ≤ ∆(G) + 1 for any connected graph.
- Not all bipartite graphs are planar; K3,3 is a non-planar bipartite graph.
Answer: