Question

1. [10 marks) Suppose a connected graph G has 10 vertices and 11 edges such that A(G) = 4 and 8(G) = 2. Let nd denote the number of vertices of degree d in G. (i) List all the possible triples (n2, N3, n4). (ii) For each triple (n2, n3, nd) in part (i), draw two non-isomorphic graphs G with n2 vertices of degree 2, në vertices of degree 3 and n4 vertices of degree 4. You need to explain why the graphs are not isomorphic to each other.

Answer 1

22. l be a connected graph with lo ventices ... and 11 edges, such that 4(a)= 4 f 8(G)=2 nd denotes the no of ventices of degreed in ..ai Now no of edge = 11 .. So total degree in G - 11x 2- . Now ng = no of ventices of deg 2 in G . .. n3 = no ü . " . " deg 3 in a na = no of a ndeg 4 in G :. So clearly na + n₂.+ 24. = 10 - ... .. 22 + 3 n3+ 4nq = 22- How multiplying equation is witte 2 we get 242 +243 +2n9 = 20 —- 242 +343 +444 = 22.- ang - 2ng 2-2 3) 13.+209 = 2. Now since na, na ido so. There are two posible solution () 13 = 2 & nq =0 s (213.-0 § Mq1 solution w is not possible as if nazo then A(a) 7 4 which is contradiction so the solution (2) "3 = 6 f na 1 is valid so the solution is 1320 uq=1 .. . = n2 =9 o so the only possible triplet is (12, 13, va) -(9,0,1).

ven p goop 99 om HA this two graph are non isomorphicle graph with io vertices , ll edges with one venter of degree 4 and othen a ventices are of degree 2. there are nou isomorphic as 1st graph. contain a 8 cyde f. 3 icle whereas the end graph contain a 7 cycle & a. 4 cycle .. -