In this paper, we consider the robust Hurwitz stability analysis problems of a single parameter-dependent matrix A(theta):=A(0)+theta A(1) over theta is an element of [-1,1], where A(0), A(1) is an element of R-nxn with A(0) being Hurwitz stable. In articular, we are interested in the degree N of the polynomial parameter-dependent Lyapunov matrix (PPDLM) of the form P(theta) Sigma(N)(i=0) theta(i) P-i that ensures the robust Hurwitz stability of A(theta) via P(theta) >0, P(theta)A(theta)+A(T)(theta)P(theta)<0(for all theta is an element of [-1,1]). On the degree of PPDLMs, Barmish conjectured in early 90s that if there exists such P(theta), then there always exists a first-degree PPDLM P(theta)=P-0+theta P-1 that meets the desired conditions, regardless of the size or rank of A(0) and A(1). The goal of this paper is to falsify this conjecture. More precisely, we will show a pair of the matrices A(0), A(1) is an element of R-3x3 with A(0)+theta A(1) being Hurwitz stable for all theta is an element of [-1,1] and prove rigorously that the desired first-degree PPDLM does not exist for this particular pair. The proof is based on the recently developed techniques to deal with parametrized LMIs in an exact fashion and related duality arguments. From this counter-example, we can conclude that the conjecture posed by Barmish is not valid when n >= 3 in general. (C) 2006 Elsevier Ltd. All rights reserved.