Purchase Solution

Self-complementary graph proof

Not what you're looking for?

Ask Custom Question

1.10 Let G be a self-complementary graph of order n, where n=1(mod 4)
Prove that G contains at least one vertex of degree (n-1)/2
(hint: Prove the stronger result that G contains an odd number of vertices of degree (n-1)/2.

Can you explain it step by step and draw a graph.

Purchase this Solution
Solution Summary

The solution provides a proof regarding a self-complementary graph.

Solution Preview

Please see the attachment.

In the graph, H is the complement graph of G. G and H are isomorphic, n = 5. G has 5 (odd) vertices with degree (n-1)/2=2. This is an example of the statement. Here is the proof.

Proof:
Suppose G is a self-complementary graph with order n, n = 1 (mod 4). H is its complementary graph. Since G is self-complementary, then G and H are isomorphic. We can find an isomorphic map p from G to H, such that (u,v) is an edge of G if and only if (p(u),p(v)) ...

Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Probability Quiz

Some questions on probability

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.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

View More Free Quizzes
Related BrainMass Solutions

  • Self-Complementary Graph

    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.

  • Probability Theory : Independent and Complementary Events Proof

    An independent and complementary events proof is provided. The solution is detailed and well presented.

  • graph theory

    Explanation: I have written the proof in a way that, to me, seems self-explanatory.

  • Complementary Angles and Systems of Equations

    157828 Complementary Angles and Systems of Equations Two angles are complementary of each other. Twice one angle is equal to the other angle plus the product of three and five. A. Set up a system of linear equations to represent the two angles.

  • Specific Therapeutic Techniques

    There is no scientific proof to date, however, of the existence of such energy fields. The technique is through manipulating biofields by applying pressure and/or manipulating the body by placing the hands in, or through, these fields.

  • effect of an increase in the price of gas

    This can be explained in the following graph. In the above figure, SS & DD refers to the original supply & demand curves for compact cars.

  • Forest and subgraph

    Note that the following proof assumes the graph is finite. Proof by contradiction: Suppose there exists a graph G which is a forest and has an induced subgraph which does not contain a vertex of degree at most one.

  • Tensile Test on As Drawn Brass

    From the graph, the 0.1% proof stress = 0.11 kN/mm^2. Test Results for 70/30 As Drawn Brass ... Modulus of elasticity = ... From the graph, the 0.1% proof stress = ...

  • Bipartite graph matching proof

    229061 Bipartite Graph Matching Proof Please help me with the proof of the question in the attached file. If G = (V, U, E) is a bipartite graph satisfying |V|=|U|=n and |N(S)|>=|S|-d for every...Hint: Try to use Hall's theorem. Proof.

View More Related Solutions