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+)
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.
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.
A self-complementary graph on 4 vertices has 3 edges, and the on on 5 vertices has 5 edges.
No need to be angry because of one typo that replaced a - with a +.
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.