I am writing a simple object to represent an edge in a graph.

Before you proceed with writing a no-argument new() constructor, consider whether an unconnected edge object would by semantically valid in your system. If not, drop that constructor.

When you can construct a system such that no object is ever in a semantically invalid state between method invocations, the system is a lot easier to test, and a lot more robust.

That said, an optional trailing parameter is easy to handle.

sub new {
    my $class = shift;
    my($from, $to, $label) = @_;
    my $self = {};
    $self->{'from_node'} = $from;
    $self->{'to_node'} = $to;
    $self->{'label'} = $label;   # which may be undef
    bless $self, $class;
}
[download]

This relies on a side-effect of assiging into a list of variables from an array: If the array is smaller than the list, unmatched variables get assigned undef.

This is less code than the named argument forms that other people are suggesting, but is also less flexible should you decide to support other edge attributes that can be set at construction time.