g | x | w | all
Bytes Lang Time Link
150Python240820T201936ZCursorCo
238Python240817T044742ZMukundan
1987Scala 3240818T120941Z138 Aspe
135Charcoal240817T124317ZNeil
643Python3240816T145138ZAjax1234

Python, 161 150 bytes

-11 bytes thanks to @xnor's idea in the comments

lambda G:len({min((H:=lambda a,b,p=G:(1,*sorted(H(n,b,a)for n in G[a]if n!=p))*([]==G[b][a!=b:]))(j,k),H(k,j))for j in sum(G,[])for k in sum(G,[])})-1

Attempt This Online!

Unnamed function which takes an adjacency list as input and outputs the number of backbones.

While I came up with the algorithm I used here independently, I did use some stuff from Mukundan314's answer, so be sure to go upvote that as well. Specifically, the idea of using an adjacency list instead of edge pairs saved at least a dozen bytes, and I'm using their code that runs the test cases as well.

Explanation

The idea started out pretty simple: Look at each pair of leaves on the graph, take a representation of the graph with them "marked" in some way, add that to a set. Then our answer will be the size of the set at the end. First we have to think about how to represent the graph; in python, nested tuples are a pretty natural choice for a tree where nodes are not distinguishable. This is also just about the only choice since to get our free deduplication from the set, we need the representation to be hashable. But how to mark the two leaves? Well we get one for free, since we have to pick a root when converting the graph to nested tuples. The other one is a little trickier. We put an integer at the beginning of every tuple except the second leaf, which we leave as an empty tuple. To keep the representations consistent for isomorphic graphs, as they are recursively generated, the tuples are sorted at every step. This means that two isomorphic graphs will have the same representation. The last bit to consider is ordering. We pick ordered pairs, but backbones are not directional. To solve this problem, we simply look at both directions, compare them, and take the "first" one. In this way we can generate a set of all backbones and we have our answer.

As for the actual code, let's start by looking at the helper function H. This is the function which generates the tuple representation of the graph given two nodes a and b. This is defined inline so it has access to the graph G, p is the previous node which is avoided to prevent backtracking.

H:=lambda a,b,p=G:          # define lambda H inline
  (1,                       # integer for first element of tuple
    *sorted(                # sort and splat elements in to tuple
      H(n,b,a)              # make a recursive call to H
      for n in G[a]if n!=p  # for each node connected to 'a' that isn't the previous node
    )                       # 
  )                         # 
  *([]==G[b][a!=b:])        # if len(G[b]) > 1 or if a==b, we return an empty tuple

That last bit there does a lot of heavy lifting. If b is not a leaf or a and b are equal at the start, we immediately return an empty tuple, meaning that this always returns an empty tuple for invalid node pairs. It also does the job of distinguishing the second leaf, since it will be the only empty tuple.

For the main function then all we need to do is iterate over all node pairs, call H on both orderings, add the "lesser" one to the set, and take the length. We subtract one from this length since all invalid node pairs will be added to the set as an empty tuple, which we can discount.

lambda G:                                   # define our main funciton
  len(                                      # take the length of
    {                                       # the set of
      min(                                  # the lesser of
        H(j,k),H(k,j)                       # H called on (j,k) in both orders
      )                                     # 
      for j in sum(G,[])for k in sum(G,[])  # iterate j and k over all nodes
    }                                       # 
  )                                         # 
  -1                                        # subtract 1 to account for invalid pairs

Python, 238 bytes

-7 bytes thanks to @Neil
-8 bytes thanks to @emanresu A
-5 bytes thanks to @xnor
+72 bytes due to a very serious bug (pointed out by @Jonathan Allan); bugged version

h=lambda g,p,n:(*sorted(h(g,n,c)for c in g[n]if p^c),)
def f(g):
 s=[]
 for*i,p,n in(q:=[[h(g,n,n),n,n]for n,c in enumerate(g)if len(c)<2]):
  q+=[[h(g,c,c),*i,n,c]for c in g[n]if p^c];s+=[(*min(i,i[::-1]),)]*(g[n]==[p])
 return len({*s})

Attempt This Online!

Takes input as an adjacency list, test runner contains code to convert edge list to adjacency list.

Scala 3, 1987 bytes

A port of @Ajax1234's Python code in Scala.

1987 bytes, it can be golfed much more.


Golfed version. Attempt This Online!

def e(edges: List[(Int, Int)]): Set[Int] = {
    edges.flatMap { case (a, b) => List(a, b) }.toSet
  }
def t[A](seq: Seq[A]): List[A] = {
    seq.toList
  }
def b(edges: List[(Int, Int)]): Map[Int, Set[Int]] = {
    edges.foldLeft(Map[Int, Set[Int]]()) { (A, edge) =>
      val (a, b) = edge
      A.updated(a, A.getOrElse(a, Set()) + b)
        .updated(b, A.getOrElse(b, Set()) + a)
    }
  }
def f(A: Map[Int, Set[Int]]): Map[List[Int], List[List[Int]]] = {
    var queue = A.filter(_._2.size == 1).keys.map(node => (node, List(node), List(A(node).size))).toList
    var paths = Map[List[Int], List[List[Int]]]()
    while (queue.nonEmpty) {
      val (currentNode, path, degrees) = queue.head
      queue = queue.tail
      var isLeaf = true
      for (neighbor <- A(currentNode) -- path.toSet) {
        queue = queue :+ (neighbor, path :+ neighbor, degrees :+ A(neighbor).size)
        isLeaf = false
      }
      if (isLeaf) {
        val d= t(degrees)
        val r= t(degrees.reverse)
        if (paths.contains(d)) {
          if (!paths(d).contains(path) && !paths(d).contains(path.reverse)) {
            paths = paths.updated(d, paths(d) :+ path)
          }
        } else if (paths.contains(r)) {
          if (!paths(r).contains(path) && !paths(r).contains(path.reverse)) {
            paths = paths.updated(r, paths(r) :+ path)
          }
        } else {
          paths = paths.updated(d, List(path))
        }
      }
    }
    paths
  }
def c(edges: List[(Int, Int)]): Int = {
    val paths = f(b(edges))
    var u= 0
    for ((degrees, pathList) <- paths) {
      var subgraphs = List[List[List[Int]]]()
      for (path<-pathList) {
        val E=edges.filter { case (a, b) => !path.contains(a) && !path.contains(b) }
        val N= e(edges).diff(e(E)).diff(path.toSet)
        val newSubgraph = f(b(E ++ N.map(node => (node, node)))).keys.toList
        subgraphs = subgraphs :+ newSubgraph.map(_.sorted)
      }
      u+= subgraphs.distinct.size
    }
    u
  }

Ungolfed version. Attempt This Online!

import scala.math.Ordering.Implicits.seqOrdering

object Main {

  def extractNodesFromEdges(edges: List[(Int, Int)]): Set[Int] = {
    edges.flatMap { case (a, b) => List(a, b) }.toSet
  }

  def toTuple[A](seq: Seq[A]): List[A] = {
    seq.toList
  }

  def buildAdjacencyList(edges: List[(Int, Int)]): Map[Int, Set[Int]] = {
    edges.foldLeft(Map[Int, Set[Int]]()) { (adjacencyList, edge) =>
      val (a, b) = edge
      adjacencyList.updated(a, adjacencyList.getOrElse(a, Set()) + b)
        .updated(b, adjacencyList.getOrElse(b, Set()) + a)
    }
  }

  def findAllPaths(adjacencyList: Map[Int, Set[Int]]): Map[List[Int], List[List[Int]]] = {
    var queue = adjacencyList.filter(_._2.size == 1).keys.map(node => (node, List(node), List(adjacencyList(node).size))).toList
    var paths = Map[List[Int], List[List[Int]]]()

    while (queue.nonEmpty) {
      val (currentNode, path, degrees) = queue.head
      queue = queue.tail

      var isLeaf = true

      for (neighbor <- adjacencyList(currentNode) -- path.toSet) {
        queue = queue :+ (neighbor, path :+ neighbor, degrees :+ adjacencyList(neighbor).size)
        isLeaf = false
      }

      if (isLeaf) {
        val degreesTuple = toTuple(degrees)
        val reversedDegreesTuple = toTuple(degrees.reverse)

        if (paths.contains(degreesTuple)) {
          if (!paths(degreesTuple).contains(path) && !paths(degreesTuple).contains(path.reverse)) {
            paths = paths.updated(degreesTuple, paths(degreesTuple) :+ path)
          }
        } else if (paths.contains(reversedDegreesTuple)) {
          if (!paths(reversedDegreesTuple).contains(path) && !paths(reversedDegreesTuple).contains(path.reverse)) {
            paths = paths.updated(reversedDegreesTuple, paths(reversedDegreesTuple) :+ path)
          }
        } else {
          paths = paths.updated(degreesTuple, List(path))
        }
      }
    }

    paths
  }

  def countUniqueSubgraphs(edges: List[(Int, Int)]): Int = {
    val paths = findAllPaths(buildAdjacencyList(edges))
    var uniqueCount = 0

    for ((degrees, pathList) <- paths) {
      var subgraphs = List[List[List[Int]]]()

      for (path <- pathList) {
        val remainingEdges = edges.filter { case (a, b) => !path.contains(a) && !path.contains(b) }
        val remainingNodes = extractNodesFromEdges(edges).diff(extractNodesFromEdges(remainingEdges)).diff(path.toSet)
        val newSubgraph = findAllPaths(buildAdjacencyList(remainingEdges ++ remainingNodes.map(node => (node, node)))).keys.toList
        subgraphs = subgraphs :+ newSubgraph.map(_.sorted)
      }
      uniqueCount += subgraphs.distinct.size
    }

    uniqueCount
  }

  def main(args: Array[String]): Unit = {
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (3, 5))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (3, 7), (7, 8))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (3, 5), (3, 6), (3, 7))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (3, 5), (5, 6), (6, 7), (6, 8), (6, 9))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (4, 5), (4, 6), (7, 8), (8, 9), (6, 9), (9, 10))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (3, 4), (4, 5), (4, 6), (6, 7), (4, 8), (8, 9), (9, 10), (9, 11), (11, 12))))
    println(countUniqueSubgraphs(List((1, 2), (2, 3), (2, 4), (4, 5), (4, 6), (6, 7), (7, 8), (7, 9))))
  }
}

Charcoal, 149 135 bytes

≔Eθ⊞O⌕AS1κθ≔EθEθυηFθFEθλF§θκ«≔E⁻§θκ⟦κλ⟧§§ημκζ≔⟦⟧εW⁻ζεF№ζ⌊μ⊞ε⌊μ§≔§ηκλε»≔ΦEθ⟦κι⟧⁼²L⊟ιζFζ«≔⁻§θ§ι⁰ιε¿εFε⊞ζ⁺⟦κ⟧ι⊞υEι§§ηκκ»UMυ⌊⟦ι⮌ι⟧ILΦυ⁼κ⌕υι

Try it online! Link is to verbose version of code. Takes input as an adjacency matrix. Explanation: Port of an earlier version of @Mukundan314's Python answer.

≔Eθ⊞O⌕AS1κθ

Convert the adjacency matrix into a modified adjacency list where each node is considered to be adjacent to itself.

≔EθEθυη

Start constructing the list representations (Charcoal doesn't really have tuples) of trees rooted at each node.

Fθ

Repeat enough times to complete all of the representations.

FEθλF§θκ«

Loop through each adjacency pair.

≔E⁻§θκ⟦κλ⟧§§ημκζ

Get a list of all of the nodes that are next steps from the current node as seen from the current node, except for the current adjacent node.

≔⟦⟧εW⁻ζεF№ζ⌊μ⊞ε⌊μ

Sort this list.

§≔§ηκλε

Save it as the current node as seen from the adjacent node.

»≔ΦEθ⟦κι⟧⁼²L⊟ιζFζ«

Start a breadth-first search for backbones with a list of all the leaves as the first element of a backbone.

≔⁻§θ§ι⁰ιε

Get a list of next nodes for the current node, excluding the previous nodes.

¿εFε⊞ζ⁺⟦κ⟧ι

If there are any then for each next node add it to the backbone so far and add the new backbone to the search.

⊞υEι§§ηκκ

Otherwise this is a leaf so save the list representation of this backbone.

»UMυ⌊⟦ι⮌ι⟧

Take the minimum of each backbone and its reverse so that they can be deduplicated.

ILΦυ⁼κ⌕υι

Deduplicate and count the backbones.

Python3, 643 bytes

F=lambda x:{J for K in x for J in K}
W=tuple
def B(g):
 D={}
 for a,b in g:D[a]={*D.get(a,[]),b};D[b]={*D.get(b,[]),a} 
 q,S=[(i,[i],[len(D[i])])for i in D if len(D[i])==1],{}
 for a,p,d in q:
  F=1
  for A in D[a]-{*p}:q+=[(A,p+[A],d+[len(D[A])])];F=0
  if F:
   if(t:=W(d))in S:
    if p not in S[t]and p[::-1]not in S[t]:S[t]=S[t]+[p]
   elif(T:=W(d[::-1]))in S:
    if p not in S[T]and p[::-1]not in S[T]:S[T]=S[T]+[p]
   else:S[t]=[p]
 return S
def f(g):
 d=B(g)
 C=0
 for i in d:
  V=[]
  for j in d[i]:
   r=[b for b in g if all(I not in b for I in j)]
   V+=[W(sorted([*B(r+[[u,u]for u in F(g)-F(r)-{*j}])]))]
  C+=len({*V})
 return C 

Try it online!