GATE 2014 CS (CS2) – Question 13

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Numerical answer

Find the maximum edges in a bipartite graph on 12 vertices.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 36 to 36

Explanation

If the two parts have a and12−a vertices, at most a(12−a) edges join them. This quadratic is maximised at a=6. Complete bipartite K₆,₆ attains **36edges**; edges within a part are prohibited.