|May 28th, 2008, 03:38 AM||#1|
Joined: Apr 2008
Why can't a vertex with degree = 1 be cut-vertex in a tree?
I read in a book that, every vertex in a tree with degree > 1 is a cut-vertex.
I wonder why degree > 1 condition should be there. Even a vertex which has degree = 1 can also be a cut-vertex. Isn't it? So, could someone please explain whether I am right or that degree > 1 condition is really required.
Just to make sure that there is no ambiguity in the discussion, I am adding the definitions from the book itself.
The vertex connectivity of a connected graph G is defined as the minimum number of vertices whose removal from G leaves the remaining graph disconnected.
A connected graph is separable if its vertex connectivity is 1. In a separable graph a vertex whose removal disconnects the graph is called a cut-vertex.
|May 28th, 2008, 06:30 AM||#2|
Joined: Oct 2007
In order for a vertex to connect two different subgraphs, it needs an edge connected to each subgraph, thus it needs degree two.
As a littlle "experiment" to help you grasp the concept, draw 2 (or 3 or 4 or...) graphs next to each other, and try to connect any number of them with 1 vertex. How many edges do you need?
Now, try to connect any two of them with 1 edge. Can you do it using an extra vertex?
The thing I don't understand is "[b]any[b] vertex with degree > 1 is a cut vertex", but it may have to do with the type of graph you're working with.
|cutvertex, degree, tree, vertex|
|Thread||Thread Starter||Forum||Replies||Last Post|
|Diagonal from 4 vertex||unwisetome3||Algebra||3||April 5th, 2012 09:51 AM|
|Convert vertex to measurement||haniftaj||Computer Science||2||December 18th, 2010 04:07 AM|
|3D vertex||john672||Algebra||0||November 18th, 2010 08:01 AM|
|numbers and vertex||Recycle98||Algebra||1||March 18th, 2010 11:56 AM|
|Finding the Vertex||l flipboi l||Algebra||7||November 24th, 2009 11:34 AM|