Question

Graph theory

a) prove that there is a 3 regular graph if n is even and n>=4

b)

Exercise 4. How many distinct graphs are there with vertex set {1,2,...,n}? How many distinct graphs are there with vertex set {1,2,...,n} and m edges? For these questions, what happens if "with vertex set {1,2,...,n}" is replaced by "with n vertices"?

thank you

Answer 1

And al we know with the Handshake temma that the sun of all degrees of the 3-regular graph is equal to 2x amount of edges. so & dag(e) = 2161 VEV For every even number 27, 4 is naap, P72. & deg (u) = 2.El 3n = 2*1E1 ver 432 = 2.EL 3.2 = 2.3p 98 we take p=23, 4. - We see that the equation 3. 2p =2.3p is true for every p. Therefore there is a 3-regular graph if nis even and no 4. waniu es we can form an edge by joining two verter from the Bet $1,2 -ny. Now we com choose a number from the set out no ways. Therefore, the number of edges is ne. Now the number of distinet graphs with nez edges is 2. je 200 As for example for n=3 tore groups are .. . > livD D we show that the maximum number of edge is a = p (San Now to form a graph of im edges and inverter we have to choose in out of c₂ , and it can be choose at Po ways. Therefore the member of distinct graph with an vertex and medges is Pen Where pan I with verted set {1,2...ne is replaced by with n vertices" till the number of distinet graths are unchanged. Here we take that the graph is a simple graph.