Problem1B

Problem1b: Suppose {G} is a simple graph on {10} vertices that is not connected. Prove that {G} has at most {36} edges. Can equality occur?

Solution: Suppose {G} has {k} connected components, where { k\geqslant 2.} We can always find a graph {G^{\prime }} with {k-1} components by adding an edge connecting two of the {k} components of {G,} and {G^{\prime }} has more edges than {G.} Hence to maximize the number of edges of {G} which is not connected, we must have {k=2.} Suppose {G} is a disjoint union of two connected components {G_{1}} and {G_{2},} and { |V(G_{1})|=m,\ |V(G_{2})|=n-m.} To maximize the number of edges, we only need let {G_{1},G_{2}} be the complete graphs. Hence the total number of edges of {G} is {\binom{m}{2}+\binom{n-m}{2}=-m(n-m)+\frac{n^{2}-n}{2}.} To maximize the number, we can either choose {m=1} or {m=n-1,} both lead to the same result {\frac{(n-1)(n-2)}{2}.} When {n=10,} then the graph {G} has at most {\frac{(10-1)(9-1)}{2}}=36 edges, and equality can occur.

Notes: I searched the key “maximal number of edges” in our library maths database, and found many papers, some of them were published on top journals! It might be interesting to make a survey of problems on this type.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: