Discrete Math Graph Help

[californiarepoman]

Having a hard time with this problem can anyone help me with it?

Random graphs are a fascinating subject of applied and theoretical research. These can be generated with a fixed vertex set V and edges added to the edge set E based on some probability model, such as a coin flip. Speculate on how many connected components a random graph might have if the likelihood of an edge (v1,v2) being in the set E is 50%. Do you think the number of components would depend on the size of the vertex set V? Explain why or why not.

 

[HallsofIvy]

Have you thought about this at all? For example, have you tried looking at examples with small numbers of vertices? if we have only one vertex, there can be NO edge (not using loops, an edge must have two vertices). With two verticds, one edges, with three vertices, three edges (the three sides of the triangle), with four vertices. six edges (the four sided of the quadrilateral and the two diagonals), with five vertices, 10 eges (the five sides of the pentagon and the five diagonals that form a "star", etc. Do you see the pattern: 1, 3, 6, 10, ... are "triangular numbers". Those are all possible edges- in this problem, each edge has probability 0.5 of being, or not being, in the figure.