We are given an undirected graph with ~N~ nodes and ~M~ edges. If Anakin and Obi-Wan are placed at two random nodes on the graph (call them nodes ~x~ and ~y~), we would like to know the probability that they will eventually reach the same node by each traveling one edge per second (if they can). First we should consider what determines whether or not a pair of starting locations ~x~ and ~y~ will yield an eventual encounter between them.

If ~x~ and ~y~ are not reachable from one another at all (in other words, if the two nodes are in different connected components of the graph), then clearly they won't ever encounter each other.

Otherwise if they are part of the same connected component, they most likely will encounter each other. However, it actually depends on the layout of the connected component. To figure out which type of components they will never encounter each other, we can try drawing ourselves some examples. Here are some you might come up with. Say ~x~ starts on a blue node, and ~y~ starts on an orange node. Each person will never end up on a chamber of the opposite colour than the colour he started on. Therefore, they will never meet if they start on opposite colours.

Note that in all of these examples, there is never an edge connecting two nodes of the same colour. This is because if such an edge were to exist, then the "parity" of their opposing movements would be broken, and it would be possible to eventually maneuver them onto the same node. In fact, this type of graph is well-known as "bipartite." A component is bipartite if and only if there exists a way to label each of its nodes with one of two colours such that no edge connects two nodes with the same colour.

If the component is bipartite and ~x~ and ~y~ both start on different colours, then this pair of starting locations will never result in a duel, since Obi-Wan and Anakin's nodes will be guaranteed to have different labels at every point in time (they'll simultaneously alternate between blue and orange every minute). If ~x~ and ~y~ would have the same label as one another or if their component is not bipartite, then an encounter can occur (which means that it certainly will within an infinite amount of time). Convince yourself that bipartite components are actually the only type of components in which a duel can never occur.

The probability of a random pair of starting positions ~(x, y)~ eventually leading to a duel is equal to the total number of starting pairs ~(x, y)~ that result in a duel, divided by the total number of possible starting pairs (equal to ~N^2~, since ~x, y~ can each take on the nodes from ~1~ to ~N~). We can do this by trying to classify each component of the graph as either bipartite or not. Breadth-first search (BFS) or depth-first search (DFS) are popular ways to do so.

Consider each connected component of the graph in turn – we will start BFS or DFSing from any node within the component, meaning trying to greedily label the component's nodes with alternating colours (say blue is ~1~ and orange is ~2~), until they've all been labelled or a conflict has been found (with a node adjacent to nodes with multiple different labels). In the latter case, the component is not bipartite, meaning that it contains ~c^2~ valid pairs of starting locations (where ~c~ is the number of nodes in it). Otherwise, it contains ~c_1^2+c_2^2~ valid pairs (where ~c_1~ and ~c_2~ are the number of nodes labelled with ~1~ and ~2~, respectively). Traversing the graph to find the connected components and attempting to label their nodes can be done in ~\mathcal O(N+M)~ time, since a node or edge never needs to be examined more than once. A program can implement this solution exactly using an adjacency list, which is an efficient way to store and traverse graphs. More readings on bipartite graphs can be found online with a quick search.