A proof of unimodality on the numbers of connected spanning subgraphs in an n-vertex graph with at least inverted right perpendicular(3-2√2)n2 + n-7-2√2/2√2inverted left perpendicular edges

Consider a connected undirected simple graph G = (V, E) with n vertices and m edges, and let N-i denote the number of connected spanning subgraphs with i (n - 1 <= i <= m) edges in G. Two well-known open problems are whether Nn-1, N-n, ... , N-m is unimodal (posed by Welsh (1971)[21]), and whether iris log concave (posed by Mason (1972)[13]). Here, a sequence of real numbers a(0), a(1), ... , a(m), is said to be unimodal if there is an index i (0 <= i <= m) such that a(0) <= a(1) <= ... <= a(i) >= a(i+1) >= ... >= a(m), and log concave if a(i)(2) >= a(i-1)a(i+1) for all indices i (0 < i < m). In this paper, for an n-vertex graph G, we prove that Nn-1, N-n, ... , N-m, is unimodal if G has at least inverted right perpendicular(3 - 2 root 2)n(2) + n - 7-2 root 2/2 root 2inverted left perpendicular edges, and log concave if n <= 7, which implies that it is unimodal as well. (C) 2009 Elsevier B.V. All rights reserved.