Purchase Solution

K-connected graph proof

Not what you're looking for?

Ask Custom Question

3.17 Let v_1,v_2,...,v_k be k distinct vertices of a k-connected graph G. Let H be the graph formed from G by adding a new vertex of degree k that is adjacent to each of v_1,v_2,...,v_k. Show k(H)=k.

k(G)=is the vertex connectivity

Purchase this Solution
Solution Summary

This is a proof regarding a k-connected graph.

Solution Preview

Note: we name the vertex joining to each of v_1,v_2,...,v_k the new vertex.

Proof. By the definition of vertex-connectivity, we need to show that we need to remove at least k vertices from H to make H disconnected.

First of all, by the construction, we know that, if we remove v_1,v_2,...,v_k from H, then the new vertex joining ...

Solution provided by:
Changping Wang, MA
Education
  • BSc , Wuhan Univ. China
  • MA, Shandong Univ.
Recent Feedback
  • "Your solution, looks excellent. I recognize things from previous chapters. I have seen the standard deviation formula you used to get 5.154. I do understand the Central Limit Theorem needs the sample size (n) to be greater than 30, we have 100. I do understand the sample mean(s) of the population will follow a normal distribution, and that CLT states the sample mean of population is the population (mean), we have 143.74. But when and WHY do we use the standard deviation formula where you got 5.154. WHEN & Why use standard deviation of the sample mean. I don't understand, why don't we simply use the "100" I understand that standard deviation is the square root of variance. I do understand that the variance is the square of the differences of each sample data value minus the mean. But somehow, why not use 100, why use standard deviation of sample mean? Please help explain."
  • "excellent work"
  • "Thank you so much for all of your help!!! I will be posting another assignment. Please let me know (once posted), if the credits I'm offering is enough or you ! Thanks again!"
  • "Thank you"
  • "Thank you very much for your valuable time and assistance!"
Purchase this Solution
Free BrainMass Quizzes
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.

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.

Multiplying Complex Numbers

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

View More Free Quizzes
Related BrainMass Solutions

  • A Nontrivial Connected Digraph

    98545 A Nontrivial Connected Digraph Prove that a nontrivial connected digraph D is Eulerian if and only if E(D) can be partitioned into subsets E_i , 1<=i<=k, where [E_i] is a cycle for each i. <= means less and equal.

  • Subgraphs

    98563 Subgraphs 3.3 Characterize those graphs with the property that every connected subgraph is an induced subgraph. The graph must be a tree, which means that the graph has no cycles inside. Proof: Suppose the graph G has a cycle u1->u2->...

  • graph theory

    Proof: Let G be a simple connected graph on n >= 3 vertices, and suppose G has a vertex v such that removing v from G results in a disconnected graph (namely, G - {v} -- which is non-trivial since n >= 3).

  • Adjacency matrix, Order and Valency

    Proof First an example, take the graph formed by the regular pentacle: Each node is connected to every other node so the valency of each node is 4 and the adjacency matrix is Note that each row and column

  • Graph Theory : Connected Graphs and Disconnected Graphs

    Definition: A graph is connected if there is a path connecting any two distinct vertices of the graph. The sharpness of a bound is the derivative of the bound. Problem #1 (a) Proof: We use mathematical induction.

  • Graphs and Vector Calculus

    If Kn, the complete graph on n vertices, is colored in such away that every edge is either red or blue, then either the red component or the blue component is connected. Proof. We proceed by induction.

  • N-connected graphs

    This is a proof regarding an n-connected graph.

  • elementary theorem in graph theory

    357802 Elementary Theorem in Graph Theory Prove the following theorem: For any graph G, either G or its complement is connected. See the attached file. Theorem For any graph G, either G or its complement is connected.

  • Double Eulerian tour

    This is a proof regarding connected graphs and double Eulerian tours.

View More Related Solutions