Dart

A little bit of googling, a little bit of Wikipedia, and so a little bit of

gave me the following which takes about 300ms.

import 'package:collection/collection.dart';
import 'package:more/more.dart';

SetMultimap<String, String> getNodes(List<String> lines) {
  var nodes = SetMultimap<String, String>();
  for (var l in lines) {
    var p = l.split('-');
    nodes[p.first].add(p.last);
    nodes[p.last].add(p.first);
  }
  return nodes;
}

part1(List<String> lines) {
  var nodes = getNodes(lines);
  var ts = nodes.keys.where((e) => e.startsWith('t'));
  var ret = <String>[];
  for (var t in ts) {
    ret.addAll(nodes[t]
        .combinations(2)
        .where((e) => nodes[e.first].contains(e.last))
        .map((e) => (([t] + e)..sort()).toString()));
  }
  return ret.toSet().length;
}

part2(List<String> lines) {
  var nodes = getNodes(lines);
  Iterable<Set<String>> useBK1(
      Set<String> R, Set<String> P, Set<String> X) sync* {
    if (P.isEmpty && X.isEmpty) {
      yield R;
      return;
    }
    for (var v in P.toSet()) {
      yield* useBK1(R.toSet()..add(v), P.intersection(nodes[v]),
          X.intersection(nodes[v]));
      P.remove(v);
      X.add(v);
    }
  }
  var vs = nodes.keys.toSet()..addAll(nodes.values.deepFlatten());
  var ret = useBK1({}, vs, {}).toList();
  var max = ret.map((e) => e.length).max;
  return ret.firstWhere((e) => e.length == max).sorted().join(',');
}