GATE ques(4.1 -4.21) Graph Theory years(1989-2006)
4.1 [GATE 1989 2 Marks] Which of the following graphs is/are planar? (see Figure) G1, G2, G3(a) G1 only(b) G1 and G2(c) G2 only(d) G2 and G3 Solution: Answer: (c) G2 onlyG1 is K3,3 – Complete bipartite graph with 3+3 vertices. By Kuratowski’s theorem K3,3 is non-planar.G2 is Cube graph – 8 vertices, 12 edges.
GATE ques(4.1 -4.21) Graph Theory years(1989-2006) Read More »