A winning move for A is to remove any single line segment.
In solving this, we also find that the following graphs are all wins for
A (apologies for the ASCII art):
oooo ooooo oooo ooooo ooo
     
oo o oo o oo
O OO
/\  
O O OO OO
\/  
O OO
These graphs are all wins for A because A can always remove a path that
leaves behind two unconnected line segments, reducing the problem to two
identical graphs, which is a forced win for A (because B moves next.)
The two graphs on the second row are the only ones you can get if you
remove any two line segments from the starting graph. Thus, for A to
remove two line segments is suicide. For A to remove one and B to remove
one is suicide for B. Thus, when A removes one segment, B must remove
two or more line segments.
Unfortunately for B, in the cases where it is allowable to remove three
or more line segments, the result is a simple path, which is a win for A.
The cases where B removes two line segments end up as one of the five
graphs on the top row or as a simple path; all wins for A. Thus, A always
wins when starting by removing any one line segment.
If A removes three or more line segments from the starting graph, the
result is either one of the graphs on the first row or a simple path.
Thus, A should not remove any more than one segment.
 Ron Parker

For a Sympathetic tetrahedrn, the value is 0, as
you say, but the options are {*,*3,*4}, the
_____
\ /
last being \ / with options


_____ ____ _____
\ \ / \ / \ \
\ , \/ , \ / , \ , , \
   
   
*3 , 0 , 0 , *2 . 0 , *
Richard Guy

My name is Richard Hoshino and I am a graduate student at Dalhousie
University in Halifax. My thesis will analyze several different "games on
graphs", extending previously known results in these games. My final
chapter was to be an analysis of an original game I created last month,
called PEG (the Path Elimination Game). Alas, as I learned earlier this
week, PEG is virtually the same game as Pathos.
In this email, I'd briefly like to describe PEG, summarize the results
that I've come up with so far, and inquire how this may be extended to
examining Pathos.
PEG is the same game as Pathos, with one exception. When a player makes
a move in PEG by removing the edges from a path, the resulting graph
*cannot* have more than one nontrivial component. Thus, while the first
five graphs on the www.mathpuzzle.com site (those are the five graphs
that have some blue edges) show legal moves in Pathos, only the first
three are legal in PEG.
My goal is to completely analyze PEG for trees, and so to simplify things,
I first considered "rooted path trees", which is a tree formed by taking k
paths with a_1, a_2, ..., a_k edges respectively, and attaching all of
these paths to a "root" vertex v. We denote such a rooted path tree
(r.p.t.) by the ktuple (a_1, a_2, ..., a_k). For example, the bipartite
graph K_{1,6} is the (1,1,1,1,1,1) rooted path tree. And here is an ASCII
drawing of a (3,5,4) rooted path tree.
.
/\
/  \
/  \
 \

(note that if k<3, then the rooted path tree is just a simple path, so let
us suppose that k >= 3).
Since PEG forbids any player from disconnecting the graph into two or more
nontrivial components, PEG is equivalent to the following variation of
nim:
We have k heaps of sizes a_1, a_2, ..., a_k, with k >= 3, and each a_i a
positive integer.
On any move, you can do one of the following:
1) remove any number of items from one heap
2) completely remove all the items from any two heaps.
The last person to play wins.
Note: eventually the game is reduced to at most two nonzero heaps, and
then the next player to play wins by removing everything (any other move
is loony).
It is very easy to show that for k=3, the second player wins PEG iff the
nim sum of a_1  1, a_2  1, and a_3  1 is equal to 0. In other words,
(a,b,c) is a Pposition iff the nim sum of a1, b1, and c1 is zero.
For k=4, I have come up with several interesting results:
Let our r.p.t be (a,b,c,d), with a >= b >= c>= d.
If d=1, then (a,b,c,d) is a Pposition iff the nim sum of a,b,c is zero.
This follows almost immediately from the k=3 case.
If c=3 and d=2, then (a,b,c,d) is a Pposition iff the nim sum of a1,
b1, c1, and d1 is zero. (In other words, iff the nim sum of a1, b1,
and 3 is zero).
Let's consider c=4 and d=2. Then using Maple, I can verify that
(9,5,4,2), (10,7,4,2), (11,8,4,2), and (13,12,4,2) are all Ppositions.
And after this point, Maple returns the following list of all Ppositions
with c=4 and d=2:
(16,14,4,2), (17,15,4,2), (20,18,4,2), (21,19,4,2), (24,22,4,2),
(25,23,4,2), (28,26,4,2), (29,27,4,2), etc.
In other words, for a>=b>=14, c=4, and d=2, we have the following result:
(a,b,c,d) is a Pposition iff the nim sum of a2, b2, c2, and d2 equals
zero.
Let's consider c=6 and d=2. Then, (9,8,6,2) is a Pposition, and for
a>=b>=10, c=6 and d=2, we have the same result as before:
(a,b,c,d) is a Pposition iff the nim sum of a2, b2, c2, and d2 equals
zero.
Finally, let's consider c=4 and d=3. Then (9,6,4,3), (10,5,4,3),
(12,11,4,3), and (13,8,4,3) are all Ppositions, and for a>=b>=14, c=4 and
d=3, we have the same result as before:
(a,b,c,d) is a Pposition iff the nim sum of a2, b2, c2, and d2 equals
zero.
This leads me to ask two questions that I am unable to resolve:
1) I see justify for the cases (c,d) = (4,2), (6,2), (4,3), that after a
certain point we have (a,b,c,d) being a Pposition iff the nim sum of a2,
b2, c2, and d2 equals zero. But why are there "anomalies" at the
beginning? How and why does this happen? Also, what is so special about
the ordered pairs (4,2), (6,2), and (4,3)?
2) Using Maple, I have made a list of all Ppositions (a,b,c,d) with
a<=30, c<=7, and d<=4. From this, I was able to find several beautiful
patterns related to the nim sum of the numbers, as described above.
However, there is absolutely nothing I see when I make certain lists, e.g.
all Ppositions with c=5 and d=2. This list is:
(12,10,5,2), (13,11,5,2), (17,14,5,2), (18,15,5,2), (19,16,5,2),
(21,20,5,2), (25,22,5,2), (26,23,5,2), (27,24,5,2), (29,28,5,2), ...
Is there a pattern here? Maybe a better question is, must there be a
pattern here? (possibly, there isn't and the other cases were just a
coincidence).
At this point, I am stuck, and would welcome any ideas. I won't tackle
k>=5 until I get a better handle on k=4.
Also, I am curious if any of this stuff helps analyze Pathos.

Beth Speich
Solution For Pathos for K5
2nd player always wins
K 5 is a pentagon inscribed inside another pentagon. Label the outer pentagon A
and the inner pentagon (i.e. star) B. A move consists of taking edges from A or a
combination of edges from A and B (there is an isomorphism of K5 that interchanges
A and B). Label the vertices of K5 15 clockwise. Thanks to the symmetry of K5,
first moves are not sepcific to vertices.
If the first player removes any number of edges from A, the second player removes
the rest of the edges of A leaving B, a Pposition for the second player.
So, the only possible moves for the first player involve taking a combination of
edges from A and B. The only possible moves that don't form a cycle are 1) AB,
2) ABB, 3) ABA, 4) ABAB, 5) ABAA, 6) ABBA
1) Player 1 removes edges 12 and 25. The second player removes edges 13, 34 and
45, leaving player 1 with a pentagon. Pposition for player 2.
2) Player 1 removes edges 12, 25, and 53. Second player removes edge 13, leaving
player 1 with bowtie, i.e. 2 triangles. Pposition for player 2.
3) Player 1 removes edges 12, 25, 54. Player 2 removes edge 14 leaving player 1
with bowtie. Pposition for player 2.
4) Player 1 removes edges 51, 13, 34, and 42. Player 2 removes edges 54, 41, and
12. Player leaves triangle; Pposition for player 2.
5) Player 1 removes edges 12, 25, 54, and 43. Player 2 removes edges 14, 42,
and 23 leaving Player 1 with triangle; Pposition for player 2.
6) Player 1 removes edges 15, 52, 24, and 43. Player 2 removes edges 14, 45 and
53 leaving player 1 with triangle; Pposition for player 2.
Thus, player 2 wins no matter what. Too bad for player 1.
St. Olaf Combinatorics Class Spring '02 under the direction of David "Games Guru"
Molnar

Daniel Hennessy and Mark Thompson also solved K33. 
Nathan Stohler demonstrated that A wins on a pentagonal prism, and B wins on the cube, and solved K3,3.
I went through all the possible moves for A to show that B always wins
the Pathos game on the cube. I started with the oneedge and twoedge
moves. We can assume all moves of three or more edges start with
346, since any two edges will do. I'm sure that some of the moves
for A are symmetric (and are repeated below), but I wanted to make sure
I covered all possible moves.

Chris Lusby Taylor
The only winning first move on K33 is to erase any one edge.
Surprisingly, any legal first move of length n leaves exactly the same
graph as any other.

Ross Cram
1. Player one (A) removes a diagonal, leaving second player w/ hexagon w/ two
diagonals.
2. Player 2 cannot remove any part of the perimeter because then, player one will
remove the rest of the perimeter leaving two disjoint line segments.
3.Player 2 cannot remove only 1 diagonal, because then player 1 will take the
other diagonal, leaving a polygon(cycle).
4. Player 2 cannot remove a diagonal and part of the perimeter because
a. player one can remove the rest of the perimeter and leave player 2 with
a polygon.
else,
b. player one can leave player two with 2 disjoint line segments
else,
c. player one takes enough of the perimeter to leave player 2 with a tree
w/ 3 line segments (a Y shape).
5. Player two cannot remove two diagonals and 1 piece of the perimeter because
player one then takes the rest of the perimeter (all that is left) and wins.
6. Player two cannot remove two diagonals and more than 1 piece of the perimeter
because player one will be left with a disjoint line segment and a path, so player
1 will take part of the path leaving player 2 with 2 disjoint line segments.
7. Player two cannot remove two diagonals and more than 1 piece of the perimeter
because player one will be left with 3 disjoint line segments, player 1 takes one
of these leaving player 2 with 2 disjoint line segments.
Q.E.D Player 1 wins
thanks,
St. Olaf College Combinatorics class (10:34am) under the observation of David
"Games Guru" Molnar

Ramprasath Lakshminarasimhan
K5  B wins
___________
Once again label the vertices in any fashion from 1 to 5.
Let N be the length of the path played by A in the first move.
Note N <= 4
N=4
Without loss of generality (wlg) let the path be 35241
B then removes 13 and gives A, a 5cycle and wins !
N=3
wlg let the path be 4135
B > 5234, giving A, a 4cycle and wins.
N=2
wlg let the path be 413
B > 42153 and again gives a 4 cycle to A !
N=1
wlg let the path be 31
B > 14253 giving a 5cycle to A and wins!
I think this proves my 1st claim.
Here I'll give you the reasoning for my claim namely:
B wins on the cube
__________________
6______________7
\ / Once again let N denote
 \__________/  the length of the path
 1 2  moved by A in the first move.
   
   
   
   
 4________3 
 / \ 
/____________\
5 8
(In all the cases below except N=4, B gives A two disconnected copies of
the same graph and wins by repeating A's moves from thereon.)
N=7
wlg let the path be 16723854
B > 2143
N=6
wlg A > 6785432
B > 56127
N=5
wlg A > 167854
B > 834127
N=4
wlg A > 16785
B > 721456
N=3
wlg A > 1672
B > 65412387
N=2
wlg A > 672
B > 3214587
N=1
wlg A > 67
B > 614387 !!
I guess that proves my claim.
And lastly, I think A's winning move for K3,3 is removing just one edge.
Is it correct ?

Jim Boyce
K5 is a secondplayer win. It is an example of a large set of
secondplayer wins. If the degree of each vertex is even, then the
second play can force a win. The first player makes some move, which
will leave two vertices of odd degree. They are, perforce, in the same
component. The second player removes some other path that connects
those two vertices. This reduces the game to a smaller graph with all
vertices of even degree.
K3,3 is a first player win. The winning move is to remove one edge. If
you remove more, then the second player can remove a path leaving 2
isolated edges.
Let's look at the seond player's possible responses. The end points of
his path can include 0, 1, or both of the endpoints of you path. That
gives us 3 cases to look at:
case 0: His path and your path had no endpoints in common. So there are
only two vertices of odd degree left. You remove any path that connects
them and win (either now, or next turn).
case 1: He extended you path to one of your losing first moves. You
remove a path leaving two isolated edges and win next turn.
case 2: he has extended your edge to a cycle.
case 2a: If it is a 6cycle, then you remove 1 edge and win next turn.
case 2b: If it is a 4cycle, then you remove a path leaving 2 isolated
edges and win next turn.