Anonymous Monk,
I saw this node just as I was leaving so I thought about it on the way home. This is actually a pretty easy problem if you turn it into a tree and I am not sure it requires Graph

#!/usr/bin/perl
use strict;
use warnings;

my %net = (
    '1.2.3.4' => ['1.2.3.5', '1.2.3.7'],    
    '1.2.3.5' => ['1.2.3.4', '1.2.3.6', '1.2.3.7'],
    '1.2.3.6' => ['1.2.3.5', '1.2.3.7'],
    '1.2.3.7' => ['1.2.3.6', '1.2.3.4', '1.2.3.5'],
);
print find_path('1.2.3.4', '1.2.3.6', %net);

sub find_path {
    my ($beg, $end, %net) = @_;
    my (%seen, %stop, @work);
    for (@{$net{$end}}) {
        return "$beg=>$end" if $_ eq $beg;
        $stop{$_} = 1;
    }
    push @work, {key => $_, path => "$beg=>$_"} for @{$net{$beg}};   
    while (@work) {
        my $node = pop @work;
        next if $seen{$node->{key}}++;
        return "$node->{path}=>$end" if $stop{$node->{key}};
        push @work, {key => $_, path => "$node->{path}=>$_"} for @{$ne
+t{$node->{key}}};
    }
    return 'path not found';
}
[download]

First thing you do is create a %stop hash that tells you when you have built enough of the tree. It will contain all of the nodes connected to $end. If one of those nodes happens to be your $beg value you return immediately.

Next you create a work queue/stack of all the nodes connected to $beg. You build the path as you go so once you have found the node you are looking for you don't have to walk the tree again.

Finally you take an item from the work queue and check to see if you have seen it before. If not you check to see if we are 1-hop away from $beg (%stop hash). If not, we go through all the nodes connected to this node and add it to our work queue. If we get to the end we know that there is no connection.