Graph Theory - Connectivity of r-regular graphs Find the minimum positive integer r for which there exists an r-regular graph G such that λ(G) ≥ κ(G) + 2
I know it's not 1,2,3-regular since κ(G) = λ(G) for those graphs.
All help appreciated.
 A: In that case, the answer must be 4 because I found such an example using Sage.
for g in graphs.nauty_geng("10 -c -d4"):
    if g.is_regular() == True:
        if g.is_clique() == False:
            connect_diff = g.edge_connectivity() - g.vertex_connectivity()
            if connect_diff >= 1:
                print g.graph6_string(), "has order", g.order(), "is", min(g.degree()), "regular and the difference is", connect_diff

Explanation the nauty_geng generates all graphs of order 10 that are connected with minimum degree at least 4.  I used this code starting at degree 4 just for completeness.  The first graph at all with a difference at least 2 is of order 10.  At order 10, there are two graphs with a difference of 2.  One is 4-regular and one is 6-regular.  The 4-regular graph is all you need, of course.
The graph is the graph with graph6 string = ICQrThiu?
It has edge connectivity 4 and vertex connectivity 2.
The vertices are 0 through 9 and the edges are given by Sage as:
[(0, 3, None), (0, 5, None), (0, 7, None), (0, 9, None), (1, 4, None),
(1, 6, None), (1, 8, None), (1, 9, None), (2, 5, None), (2, 6, None),
(2, 7, None), (2, 8, None), (3, 5, None), (3, 7, None), (3, 9, None),
(4, 6, None), (4, 8, None), (4, 9, None), (5, 7, None), (6, 8, None)]
The basic shape of the graph is as follows.  Take two 4-cliques and two other isolated vertices.  For each 4-clique, take 2 vertices and connect them to one of the isolated vertices.  Take other 2 vertices of the 4-clique and connect them to the other isolate vertex.
