Purchase Solution

odd number of edges

Not what you're looking for?

Ask Custom Question

Let G=(V,E) be a 3-regular graph (i.e. one in which all nodes have degree 3), and let S SUBSET V be any subset of the nodes such that |S| is odd. Prove that the cut delta(S) must contain an odd number of edges.

Please refer to attachment for proper formatting.

Attachments
Purchase this Solution
Solution Summary

This solution helps explore a proof for an odd number of edges.

Solution Preview

Let <S> denote the subgraph of G induced by S.

[
That is, <S> has S as the vertex set and any two vertices u and v in S are joined by an edge if and only if they are joined by an edge in G.
Refer: http://mathworld.wolfram.com/Vertex-InducedSubgraph.html
]

Now, for each vertex v in the set S, the degree of v in G is 3. ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Multiplying Complex Numbers

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

Graphs and Functions

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

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.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

View More Free Quizzes
Related BrainMass Solutions

  • Geometry

    Create a graph with four odd vertices. See attached file for full problem description. A graph vertex in a graph is said to be an odd node if its vertex degree is odd, i.e., if the number of edges the vertex is connected to is odd.

  • Eulerian Graphs

    Observation A: Let n_i denote the number of edges emerging from vertex i of graph G. If an edge of graph G connects between vertices i and j, the respective vertex of L(G) has (n_i+n_j) edges emerging from it.

  • Euler Path Problem : The Seven Bridges of Konigsberg

    edges in = number of edges out, therefore the total number of edges at the vertex is twice the number of edges in/out).

  • Euler Path Problem: Cross Bridges No More Than Once

    edges in = number of edges out, therefore the total number of edges at the vertex is twice the number of edges in/out).

  • Automata and Computability

    Then that would mean that both x and y were reached by taking an odd number of steps from the start node, or both were reached by taking an even number of steps.

  • Self-complementary graph proof

    This is a contradiction with the fact that n is odd. So G must contain at least one vertex with degree (n-1)/2. Second, I show there are odd number of vertices in G with degree (n-1)/2.

  • Use Fleury's Algorithm to find possible Euler paths

    Continue until you return to the other odd vertex. This solution consists of details of finding an Enler path using Fleury's algorithm. See in attached. An example to find possible Euler paths by Fleury's Algorithm.

  • Graph proofs

    Now there are two possibility (a)n and r are even (b) n and r are odd Suppose graph G having order n then we also know that number odd vertices are even . Since in the graph, there are only two types of vertices even and odd.

  • Relations and Graph Theory.

    Solution: Number of base 10 numbers of 3 digits = 9*10*10 = 900 Number of three-digits numbers have no two consecutive digits equal = 9*9*9 = 729 Number of three digits numbers with at least one pair of consecutive digits equal = 900-729 = 171

View More Related Solutions