Self-Complementary Graph
Not what you're looking for?
Let G be a graph. Then G = (V, E), where V and E are the vertex set and edge set, respectively, of G.
The complement of G, which we will refer to as "G bar," is the graph (V, E bar), where V is the vertex set of G bar (i.e., the vertex set of G bar is identical to the vertex set of G) and E bar is the edge set of G bar. The edge set E bar is defined as follows:
For distinct vertices v1, v2, there is an edge that connects v1 and v2 in G bar if and only if there is no edge that connects v1 and v2 in G.
Definition: A graph G is self-complementary if G is isomorphic to G bar.
Do the following:
(a) Show that the graph G = ({a, b, c, d}, {ab, bc, cd}) is self-complementary.
(b) Find a self-complementary graph with five vertices.
(c) Prove that if a self-complementary graph has n vertices, then either n is congruent to 0 (mod 4) or n is congruent to 1 (mod 4).
Purchase this Solution
Solution Summary
This solution provides step-by-step proofs of parts (a) and (c) are given, and an example of a self-complementary graph with five vertices (including a detailed justification) is provided in an attached Word document.
Solution Preview
(a) Proof that the graph G = ({a, b, c, d}, {ab, bc, cd}) is self-complementary:
By the definition of the complement of G, we have G bar = ({a, b, c, d}, {ac, ad, bd}).
To show that G is self-complementary, define a mapping f(V) -> V as follows:
f(a) = b; f(b) = d; f(c) = a; f(d) = c
Proof that f is a graph isomorphism:
f is a bijection (one-to-one, onto mapping from V to V), because every element of V is mapped (via f) to exactly one element of V, and every element of V is the image (via f) of exactly one element of V.
For every pair v1, v2 of distinct vertices in V, there is an edge connecting v1 and v2 in G if and only if there is an edge connecting f(v1) and f(v2) in G bar:
There is an edge connecting a and b in G, and an edge connecting f(a) = b and f(b) = d in G bar.
There is an edge connecting b and c in G, and an edge connecting f(b) = d and f(c) = a in G bar.
There is an edge connecting c and d in G, and an edge connecting f(c) = a and ...
Education
- AB, Hood College
- PhD, The Catholic University of America
- PhD, The University of Maryland at College Park
Recent Feedback
- "Thanks for your assistance. "
- "Thank you. I understand now."
- "Super - Thank You"
- "Very clear. I appreciate your help. Thank you."
- "Great. thank you so much!"
Purchase this Solution
Free BrainMass Quizzes
Graphs and Functions
This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.
Probability Quiz
Some questions on probability