Thread: 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+)

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 has edges.

If has vertices then .
So how many edges does have?

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.

Originally Posted by Plato

A complete graph of order has edges.

If has vertices then .
So how many edges does 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.

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.

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 +.

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.

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.