It looks some urls and installation instructions have changed recently? I had a gitlab-ci that started failing:

E: The repository 'http://downloads.skewed.de/apt/buster buster Release' does not have a Release file.

I tried following the new instructions to update the tests, and while apt-get is not complaining anymore and the installation appears to be successful, when the tests run it is not able to find graph_tool. Here is a MWE that’s failing: (I replaced my usual pytest with a simple attempt to import the library to illustrate)
(Note I’m using add-apt-repository. Previously I was using add-apt-repository -s but it seems like having the deb-src was breaking things)

  image: python:3.6-slim
  stage: test
    - apt-get update
    - apt-get install -y gnupg2 software-properties-common
    - apt-key adv --keyserver keys.openpgp.org --recv-key 612DEFB798507F25
    - add-apt-repository "deb http://downloads.skewed.de/apt buster main"
    - apt-get update
    - apt-get install -y gcc python3-dev python3-pip
    - apt-get install -y python3-graph-tool
    # - pip3 install -r requirements.txt
    - pip3 freeze
    - python3 -c 'from graph_tool.all import *'

Here is a snippet from the output. I didn’t see any error during installation (tried this both on gitlab and locally with gitlab-runner)

$ apt-get install -y python3-graph-tool
Reading package lists...
Building dependency tree...
Reading state information...
The following additional packages will be installed:
  adwaita-icon-theme at-spi2-core blt dbus-user-session
  dconf-gsettings-backend dconf-service fontconfig fontconfig-config
Need to get 115 MB of archives.
After this operation, 575 MB of additional disk space will be used.
Unpacking python3-graph-tool (2.31) ...
Setting up libxdot4 (2.40.1-6) ...
Setting up javascript-common (11) ... 

$ pip3 freeze
$ python3 -c 'from graph_tool.all import *'
Traceback (most recent call last):
  File "<string>", line 1, in <module>
ModuleNotFoundError: No module named 'graph_tool'
Running after script...
ERROR: Job failed: exit code 1
FATAL: exit code 1