2nd version of the answer...

For **SHORT**: Use an explicit favorable `method=`

, for instance...

```
networkx.algebraic_connectivity( GD, method='tracemin_lu' )
```

Possible methods are listed e.g. here:

networkx.linalg.algebraicconnectivity.algebraic_connectivity

but not all methods run smoothly (in the given example).

The **LOOONG** story, this is an edited and extended version of the first answer, where **all** eigenvalues were computed **in sage** (not in `networkx`

).
After the comment
<*Practically speaking, I don't want to compute all the eigenvalues, that's why I'm using networkx's implemented method.*>
that i fully understand and support in the meantime, had to look closer to the situation...

So the following worx for me now, and hopefully also for you:

```
import networkx
D = \
{ 0 : [ 5, 6, 11, 15, 19, 21, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
5 : [0, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
6 : [0, 5, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
11: [0, 5, 6, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
15: [0, 5, 6, 11, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
19: [0, 5, 6, 11, 15, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
21: [0, 5, 6, 11, 15, 19, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
22: [ 5, 6, 11, 15, 19, 21, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
26: [0, 5, 6, 11, 15, 19, 21, 22, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
28: [0, 5, 6, 11, 15, 19, 21, 22, 26, 31, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
31: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 32, 33, 37, 38, 39, 41, 42, 43, 44] ,
32: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 33, 37, 38, 39, 41, 42, 43, 44] ,
33: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 37, 38, 39, 41, 42, 43, 44] ,
37: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 38, 39, 41, 42, 43, 44] ,
38: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 39, 41, 42, 43, 44] ,
39: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 41, 42, 43, 44] ,
41: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 42, 43, 44] ,
42: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 43, 44] ,
43: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 44] ,
44: [0, 5, 6, 11, 15, 19, 21, 22, 26, 28, 31, 32, 33, 37, 38, 39, 41, 42, 43 ] }
GD = networkx.Graph( D )
conn = networkx.algebraic_connectivity( GD, method='tracemin_lu' )
print "Algebraic connectivity = %s" % conn
```

This gives:

```
Algebraic connectivity = 18.0
```

and is in concordance with the computation of the full spectrum of the matrix associated to the graph.
Here come complementary computations that explain place of the above $18$ in the spectrum of the laplacian matrix.

```
d = len(D)
GDLM = networkx.laplacian_matrix( GD ).todense()
# the scipy sparse matrix access is i.m.h.o. ill,
# as it took a while to discover the method todense,
# as a step in between to access the entries (!) of a scipy matrix...
GDLM = matrix( QQ, d, d, [ GDLM[ j, k ] for k in range(d) for j in range(d) ] )
GDLMEV = GDLM.eigenvalues()
GDLMEV . sort()
print ( "The Laplacian Matrix of D is:\n%s\n\nExplicitly:\n%s\n\n"
% ( GDLM, '\n'.join( str(row) for row in GDLM.rows() ) ) )
print "The EigenValues of the laplacian matrix GDLM of the graph GD of D are:\n%s\n" % GDLMEV
print "The Algebraic Connectivity is the second smallest EV in the above list, namely:\n%s" % GDLMEV[1]
```

And we get:

```
The Laplacian Matrix of D is:
20 x 20 dense matrix over Rational Field
Explicitly:
(18, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1)
(-1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1)
(0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 18, -1, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1)
(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19)
The EigenValues of the laplacian matrix GDLM of the graph GD of D are:
[0, 18, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20]
The Algebraic Connectivity is the second smallest EV in the above list, namely:
18
```

The best solution for me was (initially) to stay completely in sage,
and define the graph data `D`

as above,
and after this compute with exactity:

```
sage: EV = Graph(D).laplacian_matrix().eigenvalues(); EV.sort(); EV[1]
18
```

Two notes follow now:

Note: **Methods** that work for the given graph. I also tried:

```
sage: networkx.algebraic_connectivity( GD, method='tracemin_chol' )
---------------------------------------------------------------------------
NetworkXError Traceback (most recent call last)
:::::::::::::::::::::::::::::::::::::::::::::::::: many traceback error lines
NetworkXError: Cholesky solver unavailable.
sage: networkx.algebraic_connectivity( GD, method='lanczos' )
17.999999999999996
sage: networkx.algebraic_connectivity( GD, method='lobpcg' )
18.0
sage: networkx.algebraic_connectivity( GD, method='tracemin_lu' )
18.000000000000004
```

If we print the values, then we get `18.0`

...

Note: Some **other test graphs** with a repeated highest eigenvalue, of the same kind.

```
def testGraph( V, K ):
"""use V vertices,
the first K vertices are not connected to themselves,
but else all connections (not to self) are allowed.
"""
D = {}
R = [1..V]
X = [1..K]
for r in R:
D[r] = [ s
for s in R
if s != r and ( r not in X or s not in X ) ]
return networkx.Graph( D )
def getInfo( GD, showLaplaceMatrix=False ):
"""provide information for the graph GD,
which is e.g. constructed by the above routine testGraph
"""
d = len( GD.nodes() )
GDLM = networkx.laplacian_matrix( GD ).todense()
GDLM = matrix( QQ, d, d, [ GDLM[ j, k ] for k in range(d) for j in range(d) ] )
GDLMEV = GDLM.eigenvalues()
GDLMEV . sort()
if showLaplaceMatrix:
print GDLM
for method in ( 'tracemin_lu', 'lanczos', 'lobpcg' ):
conn = networkx.algebraic_connectivity( GD, method=method )
print "networkx :: Algebraic connectivity = %s (%s)" % ( conn, method )
print "eigenvalues: %s" % ( GDLMEV )
```

Then we have for instance:

```
sage: getInfo( testGraph( 6,2 ), True )
[ 4 0 -1 -1 -1 -1]
[ 0 4 -1 -1 -1 -1]
[-1 -1 5 -1 -1 -1]
[-1 -1 -1 5 -1 -1]
[-1 -1 -1 -1 5 -1]
[-1 -1 -1 -1 -1 5]
networkx :: Algebraic connectivity = 4.0 (tracemin_lu)
networkx :: Algebraic connectivity = 4.0 (lanczos)
networkx :: Algebraic connectivity = 4.0 (lobpcg)
eigenvalues: [0, 4, 6, 6, 6, 6]
sage: getInfo( testGraph( 8,3 ), True )
[ 5 0 0 -1 -1 -1 -1 -1]
[ 0 5 0 -1 -1 -1 -1 -1]
[ 0 0 5 -1 -1 -1 -1 -1]
[-1 -1 -1 7 -1 -1 -1 -1]
[-1 -1 -1 -1 7 -1 -1 -1]
[-1 -1 -1 -1 -1 7 -1 -1]
[-1 -1 -1 -1 -1 -1 7 -1]
[-1 -1 -1 -1 -1 -1 -1 7]
networkx :: Algebraic connectivity = 5.0 (tracemin_lu)
networkx :: Algebraic connectivity = 5.0 (lanczos)
networkx :: Algebraic connectivity = 5.0 (lobpcg)
eigenvalues: [0, 5, 5, 8, 8, 8, 8, 8]
sage: getInfo( testGraph( 23,3 ) )
networkx :: Algebraic connectivity = 20.0 (tracemin_lu)
networkx :: Algebraic connectivity = 20.0 (lanczos)
networkx :: Algebraic connectivity = 20.0 (lobpcg)
eigenvalues: [0, 20, 20, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23]
sage: getInfo( testGraph( 20, 8 ) )
networkx :: Algebraic connectivity = 12.0 (tracemin_lu)
networkx :: Algebraic connectivity = 12.0 (lanczos)
networkx :: Algebraic connectivity = 12.0 (lobpcg)
eigenvalues: [0, 12, 12, 12, 12, 12, 12, 12, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20]
```