
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 28th, 2008, 03:38 AM  #1 
Newbie Joined: Apr 2008 Posts: 20 Thanks: 0  Why can't a vertex with degree = 1 be cutvertex in a tree?
I read in a book that, every vertex in a tree with degree > 1 is a cutvertex. I wonder why degree > 1 condition should be there. Even a vertex which has degree = 1 can also be a cutvertex. 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 cutvertex. 
May 28th, 2008, 06:30 AM  #2 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 2 
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. 

Tags 
cutvertex, degree, tree, vertex 
Thread Tools  
Display Modes  

Similar Threads  
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 