I'd like any insight or references to the following two conjectures (see the glossary below for definitions):
Conjecture 1: For any string $x$, there exists a longest common subsequence of $x$ and its reversal $x^R$ that is a palindrome.
Conjecture 2: For any string $x$ over a two-letter alphabet, all longest common subsequences of $x$ and $x^R$ are palindromes.
Conjecture 2 is not true for strings over a three-letter alphabet, a counterexample being $abacbab$, which has $abcab$ and $bacba$ as longest common subsequences.
Glossary:
A string (or word) is any finite sequence of objects ("letters") drawn from some finite set (the "alphabet").
For any string $x = x_1x_2\cdots x_{n-1}x_n$ of length $n$, the reversal of $x$ is $x^R := x_nx_{n-1}\cdots x_2x_1$.
A string $x$ is a palindrome if $x = x^R$.
A string $x$ is a subsequence of a string $y$ if $x$ results from $y$ by removing zero or more letters (in arbitrary locations, closing up any gaps that result).
A longest common subsequence (LCS) of two strings $x$ and $y$ is a string $z$ that is a subsequence of both $x$ and $y$ such that no string longer than $z$ has this property. Generally, $x$ and $y$ may have several different LCSs. There is a well-known algorithm to find an LCS of two given strings that runs in quadratic time (see e.g., Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms).
Best Answer
OK. Having failed to make a counterexample, let's attempt a proof of Conjecture 1.
Suppose that $x$ and $x^R$ have a common subsequence $s$ of length $k$. This means that there are $n_1 < n_2 < \ldots < n_k$ and $m_1 > m_2 > \ldots > m_k$ such that $x_{n_i}=x_{m_i}$.
Now look for the place where they cross: $j=\max\{i\colon n_i\le m_i\}$. Terms prior to $j$ are paired with things in front of them; terms after are paired with things behind them. The $j$ term could be paired either with itself or something in front. By reversing the sequence if necessary you can assume that $j\ge k/2$. Further if $j=k/2$ you can assume that $n_j < m_j$ as otherwise by reversing the sequence you get $j=k/2+1$.
Now you can construct a palindromic subsequence: $x_{n_1}x_{n_2}\ldots x_{n_{k/2}}x_{m_{k/2}}x_{m_{k/2-1}}\ldots x_{m_1}$ in the case where $k$ is even or $x_{n_1}x_{n_2}\ldots x_{n_{(k+1)/2}}x_{m_{(k-1)/2}}\ldots x_{m_1}$ in the case where $k$ is odd.