Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 0 down vote accepted

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(, "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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.