Graph Theory - Connectivity of r-regular graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T07:49:59Z http://mathoverflow.net/feeds/question/93550 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93550/graph-theory-connectivity-of-r-regular-graphs Graph Theory - Connectivity of r-regular graphs janvdl 2012-04-09T07:46:11Z 2012-06-15T03:22:01Z <p>Hello everyone. I'm really struggling with this question. All help appreciated.</p> <p>Find the minimum positive integer r for which there exists an r-regular graph G such that λ(G) ≥ κ(G) + 2</p> <p>I know it's not 1,2,3-regular since κ(G) = λ(G) for those graphs.</p> http://mathoverflow.net/questions/93550/graph-theory-connectivity-of-r-regular-graphs/94580#94580 Answer by w g for Graph Theory - Connectivity of r-regular graphs w g 2012-04-19T23:38:08Z 2012-04-19T23:38:08Z <p>Take tow disjoint copies of the complete graph on 5 vertices. Pick a vertex on each of the copy and split into tow vertices of degree 2. Match the the degree 2 vertices of both copies the identify them to get 4-regular, 4-egde-connected, and 2-vertex-connected graph. </p>