Is this graph a tree?

Question

Given an undirected graph, find out if it is a tree.

A tree is an undirected graph in which there is exactly one path between any two vertices. In other word, the graph is both acyclic and connected.

Input

You can take input in any reasonable format. Here are some example formats:

• an adjacency matrix, e.g., [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]];
• an adjacency list, e.g., {1:[2,3],2:[1,3,4],3:[1,2],4:[2]};
• an edge list, e.g., [(1,2),(1,3),(2,3),(2,4)];
• a built-in graph object, e.g., Graph[{1,2,3,4},{1<->2,1<->3,2<->3,2<->4}] in Mathematica.

All the above examples represent the following graph, which is not a tree:

1---2---4
 \ /
  3

Here I use numbers 1,2,3,4 to represent the vertices. You may also use, for example, 0,1,2,3.

You may assume that:

• The graph is non-empty.
• The graph has no loop (an edge connecting a vertex with itself) or multi-edge (two or more edges that connect the same two vertices).
• Each vertex is connected to at least one other vertex.

Output

A value representing whether the graph is a tree. You can choose to

• output truthy/falsy using your language's convention (swapping is allowed), or
• use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

This is code-golf, so the shortest code in bytes wins.

Testcases

Here I take inputs as edge lists.

Truthy

[(1, 2)]
[(1, 2), (2, 3), (2, 4)]
[(1, 2), (2, 3), (3, 4), (4, 5)]
[(1, 2), (1, 3), (2, 4), (2, 5)]
[(1, 3), (1, 6), (1, 7), (2, 3), (2, 5), (4, 7)]

Falsy

[(1, 2), (3, 4)]
[(1, 2), (1, 3), (2, 3), (2, 4)]
[(1, 2), (1, 3), (2, 3), (4, 5)]
[(1, 3), (1, 5), (2, 3), (3, 4), (4, 5)]
[(1, 2), (3, 4), (3, 5), (4, 5), (4, 7), (6, 7)]

Answer 1

Jelly, 7 6 5 4 bytes (thanks @Jonathan Allan!)

ṖÆḊ’

Try it online!

Ṗ      Delete the last row of the input matrix
 ÆḊ    Compute sqrt(det(A A^T)), where A is the result of the previous step
   ’   Decrement

Accepts the oriented incidence matrix of the graph. Based on Kirchhoff's Theorem, the fact that a graph has exactly one spanning tree if and only if it's a tree graph, and the fact that the Laplacian matrix of a graph can be easily computed from its oriented incidence matrix as follows: $$L=BB^T$$ where L is the Laplacian matrix and B is the oriented incidence matrix. Outputs a truthy value if the graph is not a tree, and a falsy value if it is.

After deleting the last row from the incidence matrix (Ṗ) and multiplying by its transpose, the result will be equal to the Laplacian matrix with the last row and last column deleted: exactly what we need. ÆḊ transposes, multiplies, and computes the determinant for us: perfect! It also takes the square root of the result, but for reasons I'll explain later, this isn't a problem.

The determinant of the matrix product mentioned previously, the square of the result of all but the last step, is the number of spanning trees of the graph. This is 0 for a non-fully-connected graph, 1 for a tree, and 2 or more for a fully-connected non-tree graph. Now, I mentioned that ÆḊ takes the square root of the determinant. Is this a problem? It isn't, since the square root of 0 is 0, the square root of 1 is 1, and the square root of a number greater than 1 will also be a number greater than 1. Therefore, after decrementing (’), the result will be falsy (0) if and only if the determinant is 1: that is, if and only if the graph is a tree graph.

If the number of nodes happens to be one greater than the number of edges, deleting the last row will result in a square matrix. In this case, ÆḊ will simply compute the determinant, so won't this lead to incorrect outputs? It won't, since for a square matrix A: $$\sqrt{\det(A A^T)} = \sqrt{\det(A) \det(A^T)} = \sqrt{\det(A) \det(A)} = |\det(A)|$$ Therefore, the result will still be exactly what we need (since the determinant of the matrix in question is guaranteed to be non-negative).

Answer 2

Python NumPy, 49 bytes

lambda M:M.sum()<2*len(M)*(M**0-M/M.size).I.all()

Attempt This Online!

Takes adjacency matrix as input.

How

We check two things:

1. number of edges is number of vertices - 1
2. graph is connected

To check 2 we use

1. powers M^n of the adjacency matrix describe paths of length n
2. the graph will be connected iff the sum I + M + M^2 + M^3 + ... has no zero elements. (We can always scale M so that this sum converges.)
3. the sum in 2 is a geometric series and can be written as (I-M)^-1

Python NumPy, 43 bytes (@Command Master)

lambda M:M.sum()<3*len(M)*(M**len(M)).all()

Attempt This Online!

This requires the main diagonal to be set in the input.

Answer 3

Wolfram Language (Mathematica), 10 bytes

TreeGraphQ

Try it online!

So I find a builtin in Mathematica... (my first Mathematica answer btw :D)

Answer 4

05AB1E, 14 13 bytes

ZLœεIk€à{āQ}à

Try it online!

-1 thanks to @Kevin Cruijssen

Takes input as an edge list, with vertices indexed 1,2,3,...,n.

Explanation

Uses the fact that a graph is a tree iff there's a way to order its vertices such that all but one appear exactly once as the maximum value in some edge. Proof:

• The minimum value in each connected component won't appear, so if there's only one value missing there must be a single connected component.
• If there's a cycle there must be more then \$n-1\$ edges, so the list of the maximum value in each won't be of length \$ n-1 \$.
• If the graph is a tree, its preorder scan would satisfy the condition.

Z       push the maximum value in the edge list, the size of the graph
L       push the list [1, 2, ..., n]
œ       push all permutations of it
ε       map each permutations to:
 I       push the input
 k       find the index of each vertex in each edge in the given permutation, 0-based
 ۈ      find the maximum value in each pair
 {       sort that list
 ā       push the list [1, 2, ..., len(arr)]
 Q       and compare it to the sorted list of indices
}
à        take the maximum value - return 1 if any of the values are 1, else 0

Answer 5

K (ngn/k), 26 bytes

{&//{|/'x*\:x}/x&~2-/3-/x}

Try it online!

The input is an adjacency matrix with 1s along the diagonal and symmetric with respect to transposition.

The condition tested is: the total number of 1s in the adjacency matrix is \$3n-2\$ and its transitive closure consists only of 1s.

{ } function with implicit argument x

3-/ subtract all rows of the matrix from the constant 3. The 3 will be broadcast to match the length of a row, so it's effectively \$3n\$. The result is a vector.

2-/ subtract the items of the vector from the constant 2. The result is a scalar: \$(\sum_i\sum_j A_{ij})-3n+2\$.

~ "not", i.e. "is equal to 0?"

x& "and" with the original matrix, i.e. zero it if the first condition is not true

{|/'x*\:x}/ transitive closure

• { }/ repeat until convergence

• x*\:x a 3d array of the matrix's row-by-column products

• |/' boolean or-sum of each

&// boolean and over the entire matrix

Answer 6

MATL, 11 bytes

ZyGRzQ=GYeh

This uses the same approach as loopy walt's Python/Numpy answer.

Input is a square logical matrix, where entries T and F denote true and false respectively. This represents the adjacency matrix of the graph.

Output is a truthy/falsy value, specifically a non-empty array of zeros and ones, which is truthy if and only if if it does not contain any zero.

Try it online! Or verify all test cases (footer includes truthiness/falsihood test)

How it works

Zy    % Implicit input: square matrix. Size: gives a two-element row vector
GR    % Push input again. Take the upper triangular part
zQ    % Number of nonzeros. Add 1
=     % Are they equal? Element-wise
G     % Push input again
Ye    % Logical version of matrix exponential. This computes A*e^A, where A
      % is the adjacency matrix, replacing non-zero entries by 1 (and
      % avoiding numerical precision issues). The result indicates for each 
      % node which nodes it is connected to
h     % Concatenate horizontally. This reshapes into a row vector (the two
      % concatenated arrays are a row vector and a square matrix). Implicit
      % display

Answer 7

Ruby, 53 bytes

->l{*r=1;l.all?{|a,b|(a==l||r!=r-=[l=a])&&r!=r|=[b]}}

Try it online!

Assume the list is sorted.

Answer 8

Charcoal, 26 bytes

ＷΦ⁻θυ∨¬υ⁼¹ΣＥκ⊙υ№ξμ⊞υ⊟ι¬⁻θυ

Try it online! Link is to verbose version of code. Takes an edge list as input and outputs a Charcoal boolean, i.e. - for a tree, nothing if not. Identifies non-trees with multi-edges and non-trees with loops if they are not the last edge on the list. Explanation:

ＷΦ⁻θυ∨¬υ⁼¹ΣＥκ⊙υ№ξμ

Except on the first iteration, only consider those edges where exactly one vertex has been previously visited. While at least one such edge exists...

⊞υ⊟ι

... mark one of those edges has having been visited.

¬⁻θυ

Check that there are no unvisited edges left. An edge may remain unvisited if it is part of a cycle (in which case both of its vertices will have become visited) or if it is disconnected (in which case neither of its vertices were visited). If neither holds then the original graph was a tree.

Answer 9

Vyxal, 13 bytes

LÞefA?LT*?f∑>

Try it Online!

Takes input as an adjacency matrix with 1s on the main diagonal. Port of @loopy walt's second answer from @Command Master, upvote that!

LÞefA?LT*?f∑>
L             # Get the length of the input
 Þe           # Matrix exponentiate it to that
   f          # Flatten
    A         # Are all non-zero? Call this X
     ?L       # Get the length of the input again
       T      # Triple it (multiply by 3)
        *     # Multiply this by X. Call this Y
         ?f∑  # Get the flattened sum of the input
            > # Is Y greater than this?

Jelly, 13 12 bytes

æ*LȦ×L×3>ẎS$

Try it online!

-1 byte thanks to Jonathan Allan.

Same.

æ*LȦ×L×3>ẎS$
æ*           - Matrix exponentiate the input to...
  L          - Its length.
   Ȧ         - After flattening, are they all non-zero?
    ×L       - Multiply this by the length of the input.
      ×3     - Multiply by 3.
        >    - Is this greater than...
         ẎS$ - The flattened sum of the input?

Answer 10

Jelly, 14 bytes

ŒPḊFQLƊ_LƊ€ȧ/’

A monadic Link that accepts an edge list and yields a zero (falsey) if a tree or a non-zero integer (truthy) if not a tree.

Try it online! Or see the test-suite.

How?

We know that (a) the number of edges must be exactly one less than the number of vertices and (b) there must be no sub-graph (including the whole graph, but excluding the empty graph) which has the same number of vertices and edges. So this finds the difference between vertex count and edge count for every non-empty set of edges, checks that all are non-zero and that the result for the full set of edges is \$1\$.

ŒPḊFQLƊ_LƊ€ȧ/’ - Link: list of edges
ŒP             - get the powerset of the edges (N.B. full-set is rightmost)
  Ḋ            - dequeue (removes the empty set)
          €    - for each:
         Ɗ     -   last three links as a monad:
      Ɗ        -     last three links as a monad:
   F           -       flatten the current set of edges
    Q          -       deduplicate -> distinct vertices used by this set of edges
     L         -       length -> vertex count
        L      -     length of this set of edges -> edge count
       _       -     subtract -> vertex count - edge count
            /  - reduce by:
           ȧ   -   logical AND -> 1 if a tree, 0,2,3,... otherwise
             ’ - decrement -> zero (falsey) if a tree non-zero (truthy) otherwise

---

If one takes an adjacency matrix with all vertices also identified as self-connected \$12\$ bytes is possible - see Steffan's answer.

---

If one takes the Laplacian matrix then \$6\$ bytes is possible - see Alex's answer.

Answer 11

Python, ^{108 102} 95 bytes

f=lambda g,s=0,v={0}:(v.add(s),[f(g,c)for c in g[s]-v],len(v)==len(g)==sum(map(len,g))//2+1)[2]

Attempt This Online!

Program to convert edge list to adjacency list can be found here

Answer 12

JavaScript (ES6), 69 bytes

Expects a 0-indexed adjacency list. Returns false for a tree, or true otherwise.

a=>a.some(g=(b,i,m,k=i/i)=>b.map(j=>k-=m^(q=m|1<<i)&&!g(a[j],j,q))|k)

Try it online!

Commented

a =>               // a[] = adjacency list
a.some(            // for each entry in a[]:
g = (              //   invoke the recursive function g taking:
  b,               //     b[] = adjacent vertices at the current position
  i,               //     i   = current position
  m,               //     m   = bitmask of visited vertices
  k = i / i        //     k   = counter initialized to 1 if i > 0,
) =>               //           or to NaN if i = 0
  b.map(j =>       //   for each vertex j in b[]:
    k -=           //     decrement k if:
      m ^ (        //       i was not already visited, i.e. m is not equal
        q =        //       to the new bitmask q where
        m | 1 << i //       i is marked as visited
      ) &&         //       and
      !g(          //       the result of this recursive call is 0:
        a[j],      //         list of adjacent vertices at the new position
        j,         //         new position
        q          //         updated bitmask of visited vertices
      )            //       end of recursive call
  ) | k            //   end of map(); return k, which is 0 if one and only
                   //   one path to the root was found, or still NaN if the
                   //   root was already reached, or non-zero'ish otherwise
)                  // end of some()

Answer 13

JavaScript (Node.js), 59 bytes

c=>c[(g=(i,p)=>c[i].every(j=>j==p||c[t++]&&g(j,i)))(t=1)*t]

Try it online!

Input as 0-indexed adjacency list. Output falsy for a tree, truthy otherwise.

c=>  // input 0-indexed adjacency list
c[
  (g=              // function `g` returns `false` if any
                   //   circular paths are found
                   // And after function `g`, the global
                   //   variable `t` is set to the number
                   //   of node we visited, or in the other
                   //   word, the number of nodes in the tree
    (i,            // Starting from node `i`
     p)=>          // Do not go back to previous node `p`
                   //   or the "parent" node `p` if we consider
                   //   it as a tree
                   // `p` is initialed to `undefined`, as root
                   //   node do not have a parent
    c[i].every(    // `c[i]` is all nodes connected to `i`
      j=>          // For all nodes `j` that connected to `i`
        j==p||     // if the node is not the parent node
        c[t++]&&   // we visit the node `j`
                   // increase the counter of node visited `t`
                   // for a graph contains `n` nodes, if this is
                   //   the `n+1`th node we visit, we know there
                   //   a circular in the graph. We use `c[t]` to
                   //   detect it and report falsy
        g(j,i)     // we visit the following node `j`
))(
  t=1              // Mark node `1` as visited, so initial `t` to 1
)                  // Visit the graph starting from node `1`
                   // As graph in this question would at least
                   // contains 2 nodes, we can safely use node
                   // `1` as the initial node
*t]                // If there is a loop, `false*t` is `0`
                   //   And `c[0]` is always truthy
                   // If there is not a loop, `true*t` is `t`
                   //   If all nodes are connected, the number of
                   //     nodes we visited is the number of nodes
                   //     in the graph. As nodes are 0-indexed,
                   //     `c[t]` is `undefined`, which is falsy
                   //   If some nodes are not connected to node `1`,
                   //     the number of nodes we visited is less
                   //     than the number of nodes in the graph.
                   //     And `c[t]` would be truthy.

---

JavaScript (Node.js), 66 bytes

m=>(g=(i,p,j=-1)=>m.map(r=>r[++j!=p&&i]&&m[t++]&&g(j,i))|t-j)(t=0)

Try it online!

Input a 0/1 matrix. Output falsy for a tree, truthy otherwise.

m=>(
g=(     // search the matrix
  i,    // start from node `i`
  p,    // with previous node is `p`
  j=-1  // index of inner loop, initial to -1
)=>m.map(r=>( // for each nodes that
  r[++j!=p&& // not the one where we come from
    i]&&     // and is connected to `i`
  m[t++]&& // increase counter for visited nodes `t`
           // if we had visited `length+1` nodes, there is a loop
           //     and we should stop here
  g(j,i) // visit the next node `j`
))|t-j   // return 0 if we visited every nodes once
)(
t=0        // initial count of node visited to `0`
           // as node `0` is not counted into `t`
           // the final `t` is "how many nodes we visited" - 1
)

Answer 14

C (clang), 177 bytes

r,q,*o,*z;c(v,p,i){for(q|=1<<v;i--;)z[v]&1<<i?q&1<<i?r|=i^p:c(i,v,9):0;}f(*s){z=calloc(9,4);q=r=0;for(o=s;*o;o+=2)z[*o]|=1<<o[1],z[o[1]]|=1<<*o;for(c(*s,0,9);*++s;)r|=~q&1<<*s;}

Try it online!

-7 bytes thanks to ceilingcat.

Function c recursively checks for cyclicity in the graph and then we simply see if all the vertices were visited.

Caveat:

Only works for vertices numbered 1 to 8