# CARMA Discrete Mathematics Instructional Seminar

## 3:00 pm

## Thursday, 25^{th} Oct 2012

**V129, Mathematics Building**

# Prof. Brian Alspach

(CARMA, The University of Newcastle)
*Gallai's 1966 conjecture on path decompositions*

In 1966 Gallai conjectured that a connected graph of order n can be decomposed into n/2 or fewer paths when n is even, or (n+1)/2 or fewer paths when n is odd. We shall discuss old and new work on this as yet unsolved conjecture.