undirected graph questions

Printable View

February 7th 2013, 11:08 AM
globalpro

undirected graph questions

a. Let G be an undirected graph with n vertices. If G is isomorphic, to its own complement how many edges must G have? (Such a graph is called self-complementary.)

b. Find an example of a self-complementary graph on four vertices and one on five vertices.

c. If G is a self-complementary graph on n vertices, where n > 1, prove that n=4k or n=4k+1, for some k∈Z+ (I think this is k subset of Z+)
February 7th 2013, 12:09 PM
Plato

Re: undirected graph questions

Quote:

Originally Posted by globalpro

a. Let G be an undirecthed graph with n vertices. If G is isomorphic, to its own complement how many edges must G have? (Such a graph is called self-complementary.)

A complete graph of order $n,~\mathcal{K}_n$ has $\binom{n}{2}=\frac{n(n+1)}{2}$ edges.

If $\mathcal{G}$ has $n$ vertices then $\mathcal{G}\cup\overline{\mathcal{G}}=\mathcal{K}_ n$ .
So how many edges does $\mathcal{G}$ have?
February 7th 2013, 01:10 PM
globalpro

Re: undirected graph questions

Thanks
I really don't remember group theroy from 50 years ago. Some of the notations just don't make sense and I think that is the problem.

So the answer to (b) for the 4 V would be a 10 edge solution and for the 5 V it would be 15 edges.

And on (c) since I don't know what k or Z represent, best guess would be G has k subgraphs and Z represents all the possibles

I told my grandson that when he asked for my help in the first place.
February 8th 2013, 11:16 AM
globalpro

Re: undirected graph questions

Quote:

Originally Posted by Plato

A complete graph of order $n,~\mathcal{K}_n$ has $\binom{n}{2}=\frac{n(n+1)}{2}$ edges.

If $\mathcal{G}$ has $n$ vertices then $\mathcal{G}\cup\overline{\mathcal{G}}=\mathcal{K}_ n$ .
So how many edges does $\mathcal{G}$ have?

How many kids have you helped flunk? Luckily I drew out the graphs and realized that the true answer is n(n-1)/2 for the number of edges on a undirected graph. Now do you have any suggestions on the C. portion of the question?

c. If G is a self-complementary graph on n vertices, where n > 1, prove that n=4k or n=4k+1, for some k∈Z+ (I think this is k subset of Z+) Maybe you can mislead me enough that I can answer it for him.
February 8th 2013, 04:35 PM
emakarov

Re: undirected graph questions

Quote:

Originally Posted by globalpro

So the answer to (b) for the 4 V would be a 10 edge solution and for the 5 V it would be 15 edges.

A self-complementary graph on 4 vertices has 3 edges, and the on on 5 vertices has 5 edges.

Quote:

Originally Posted by globalpro

How many kids have you helped flunk? Luckily I drew out the graphs and realized that the true answer is n(n-1)/2 for the number of edges on a undirected graph.

No need to be angry because of one typo that replaced a - with a +.

Quote:

Originally Posted by globalpro

c. If G is a self-complementary graph on n vertices, where n > 1, prove that n=4k or n=4k+1, for some k∈Z+ (I think this is k subset of Z+) Maybe you can mislead me enough that I can answer it for him.

Here k is the number of edges (this is not a part of the problem statement; it is a hint). Also, use (a generalization of) Euclid's lemma.
February 8th 2013, 07:22 PM
johng

Re: undirected graph questions

If two graphs are isomorphic, they both have the same number of edges. As Plato points out, then the number of edges of a self-complmentary graph must be n(n-1)/4, where n is the number of vertices. (the complete graph on n vertices has n(n-1)/2 edges). So for part c, n(n-1)/4 must be an integer. Suppose n is of the form 4k+2 with k an integer, then n(n-1)/4=(4k+2)(4k+1)/4=(2k+1)(2k+1/2)=4k^2+3k+1/2. If this last expression were an integer, 1/2 would be an integer,
tilt. Similarly, if n=4k+3. So the only possibilities left are n=4k or n=4k+1.

If you know about congruence of integers, namely a is congruent to b mod m iff m divides a-b. It's much easier to compute mod 4.