Why would a cross-compilation build fail on openssl when openssl is not in the dependency graph?

It is in the dependency graph for the target you are building for.

When using cargo tree, you need to include the target that you are building for using the --target command line option. In addition, you can use -i and a search string to know exactly which crates are bringing in the dependency:

% cargo tree --target x86_64-unknown-linux-musl -i openssl-sys
openssl-sys v0.9.58
├── native-tls v0.2.6
│   ├── hyper-tls v0.3.2
│   │   └── reqwest v0.9.24
│   │       └── depz v0.1.0 (/private/tmp/depz)
│   ├── mysql v20.1.0
│   │   └── depz v0.1.0 (/private/tmp/depz)
│   └── reqwest v0.9.24 (*)
└── openssl v0.10.30
    └── native-tls v0.2.6 (*)

Reqwest lists OpenSSL as a requirement on Linux due to it using native-tls, which depends on openssl. You need to install the pkg-config and libssl-dev packages:

sudo apt-get install pkg-config libssl-dev