Homework Help is Here – Start Your Trial Now!
Science
Advanced Physics
Suppose G is a simple undirected graph with n vertices. If G is self-complementary, prove that either n = 4t or n = 4t +1 for some t e Z+.

Suppose G is a simple undirected graph with n vertices. If G is self-complementary, prove that either n = 4t or n = 4t +1 for some t e Z+.

icon
Related questions
Question

Please show step by step explanations. Thank you.

1. Suppose G is a simple undirected graph with n vertices. If G is self-complementary, prove that either n = 4t or n = 4t +1 for some t e Zt.
Transcribed Image Text:1. Suppose G is a simple undirected graph with n vertices. If G is self-complementary, prove that either n = 4t or n = 4t +1 for some t e Zt.
Expert Solution
Step 1

Let G be a self-complementary graph with n vertices, for n vertices their are n2 possible edges, as G is assumed self-complimentary, it follows the number of edges of G and its compliment are equal, so the edges in G must be given by 12n2, hence n2  must be even.

Let e be number of edges in G then,

e=12n2e=12n2!(n-2)!e=14n(n-1)         (2)Since,  e∈ℤ+It follows from (1) that either n or (n-1) should be a multiple of 4 for e to be a integer.

trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer