Three-connected graphs whose maximum nullity is at most three

For a graph G=(V,E) with vertex-set V={1,2,…,n}, let be the set of all n×n real-valued symmetric matrices A which represent G. The maximum nullity of a graph G, denoted by M(G), is the largest possible nullity of any matrix . Fiedler showed that a graph G has M(G)1 if and only if G is a path. Johnson et al. gave a characterization of all graphs G with M(G)2. Independently, Hogben and van der Holst gave a characterization of all 2-connected graphs with M(G)2. In this paper, we show that k-connected graphs G have M(G)k, that k-connected partial k-graphs G have M(G)=k, and that for 3-connected graphs G, M(G)3 if and only if G is a partial 3-path.