MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 added 2-connected; added 9 characters in body

Choose a graph $X$ with vertices $u$ and $v$ such that $X\backslash u$ and $X\backslash v$ are cospectral. (In this case I say that $u$ and $v$ are cospectral vertices.) Assume that there is no automorphism of $X$ that swaps $u$ and $v$. Now form the graph $Y$ from two copies of $X$ by identifying vertex $u$ in the first copy with vertex $u$ in the second, and vertex $v$ in the first with $v$ in the second. Next form $Z$ from two copies of $X$ by identifying $u$'s with $v$'s.

If $u$ and $v$ are adjacent, then then will be a double edge, so we assume that $u$ and $v$ are not adjacent. This means that $Y$ and $Z$ are related by a Whitney flip and hence they have the same cycle matroid.

The graphs $Y$ and $Z$ are cospectral. This follows from Corollary 4.3.2 in my book "Algebraic Combinatorics". Since we only need examples we do not need the proof though, we can just carry out the construction and check.

As example, use Schwenk's tree, constructed as follows. Start with the path on 8 vertices 0,1,...,7 and add a vertex 8 adjacent to 5. Vertices 3 and 6 are cospectral. The graphs we get from the construction are not cospectral. (I just checked using sage.)

For more examples, take any strongly regular graph with trivial automorphism group and take $u$ and $v$ to be two nonadjacent vertices. These examples will be 2-connected.

show/hide this revision's text 2 added citation

Choose a graph $X$ with vertices $u$ and $v$ such that $X\backslash u$ and $X\backslash v$ are cospectral. (In this case I say that $u$ and $v$ are cospectral vertices.) Assume that there is no automorphism of $X$ that swaps $u$ and $v$. Now form the graph $Y$ from two copies of $X$ by identifying vertex $u$ in the first copy with vertex $u$ in the second, and vertex $v$ in the first with $v$ in the second. Next form $Z$ from two copies of $X$ by identifying $u$'s with $v$'s.

If $u$ and $v$ are adjacent, then then will be a double edge, so we assume that $u$ and $v$ are not adjacent. This means that $Y$ and $Z$ are related by a Whitney flip and hence they have the same cycle matroid.

The graphs $Y$ and $Z$ are cospectral. I believe this This follows from results Corollary 4.3.2 in my book "Algebraic Combinatorics", but I am travelling and cannot supply a citation now. Since we only need examples we do not need the proof though, we can just carry out the construction and check.

As example, use Schwenk's tree, constructed as follows. Start with the path on 8 vertices 0,1,...,7 and add a vertex 8 adjacent to 5. Vertices 3 and 6 are cospectral. The graphs we get from the construction are not cospectral. (I just checked using sage.)

For more examples, take any strongly regular graph with trivial automorphism group and take $u$ and $v$ to be two nonadjacent vertices.

show/hide this revision's text 1

Choose a graph $X$ with vertices $u$ and $v$ such that $X\backslash u$ and $X\backslash v$ are cospectral. (In this case I say that $u$ and $v$ are cospectral vertices.) Assume that there is no automorphism of $X$ that swaps $u$ and $v$. Now form the graph $Y$ from two copies of $X$ by identifying vertex $u$ in the first copy with vertex $u$ in the second, and vertex $v$ in the first with $v$ in the second. Next form $Z$ from two copies of $X$ by identifying $u$'s with $v$'s.

If $u$ and $v$ are adjacent, then then will be a double edge, so we assume that $u$ and $v$ are not adjacent. This means that $Y$ and $Z$ are related by a Whitney flip and hence they have the same cycle matroid.

The graphs $Y$ and $Z$ are cospectral. I believe this follows from results in my book "Algebraic Combinatorics", but I am travelling and cannot supply a citation now. Since we only need examples we do not need the proof though, we can just carry out the construction and check.

As example, use Schwenk's tree, constructed as follows. Start with the path on 8 vertices 0,1,...,7 and add a vertex 8 adjacent to 5. Vertices 3 and 6 are cospectral. The graphs we get from the construction are not cospectral. (I just checked using sage.)

For more examples, take any strongly regular graph with trivial automorphism group and take $u$ and $v$ to be two nonadjacent vertices.