Return to Question

A connected graph is a graph that contains a path between any two vertices.

###Challenge

Build a [2-input NAND-gate] circuit that determines whether a 4-vertex graph is connected.
(A gate's 2 inputs can be the same input bit or other gate.)
Output True if the graph is connected, and False otherwise.

###Input

The six possible edges of a simple graph with 4 vertices:

[ ₀e₁ , ₀e₂ , ₁e₂ , ₀e₃ , ₁e₃ , ₂e₃ ​]

where _ae_b represents whether there is an edge between vertices a and b

Connectedness is equivalent to the following conditions:

• If less than 3 inputs are True then output False.

• If more than 3 inputs are True then output True.

• If exactly 3 inputs are True and they form a triangle then output False.

• Otherwise, output True.

The answer that uses the fewest gates wins. ​ Ties will be broken by
the lowest circuit depth (length of longest path(s) from input to output).

A connected graph is a graph that contains a path between any two vertices.

Challenge

Build a [2-input NAND-gate] circuit that determines whether a 4-vertex graph is connected.
(A gate's 2 inputs can be the same input bit or other gate.)
Output True if the graph is connected, and False otherwise.

Input

The six possible edges of a simple graph with 4 vertices:

[ ₀e₁ , ₀e₂ , ₁e₂ , ₀e₃ , ₁e₃ , ₂e₃ ​]

where _ae_b represents whether there is an edge between vertices a and b

Connectedness is equivalent to the following conditions:

• If less than 3 inputs are True then output False.

• If more than 3 inputs are True then output True.

• If exactly 3 inputs are True and they form a triangle then output False.

• Otherwise, output True.

The answer that uses the fewest gates wins. ​ Ties will be broken by
the lowest circuit depth (length of longest path(s) from input to output).

A connected graph is a graph that contains a path between any two vertices.

###Challenge

Build a [2-input NAND-gate] circuit that determines whether a 4-vertex graph is connected.
Output True if the graph is connected, and False otherwise.

###Input

The six possible edges of a simple graph with 4 vertices:

[ ₀e₁ , ₀e₂ , ₁e₂ , ₀e₃ , ₁e₃ , ₂e₃ ​]

where _ae_b represents whether there is an edge between vertices a and b

Connectedness is equivalent to the following conditions:

• If less than 3 inputs are True then output False.

• If more than 3 inputs are True then output True.

• If exactly 3 inputs are True and they form a triangle then output False.

• Otherwise, output True.

The answer that uses the fewest gates wins. ​ Ties will be broken by
the lowest circuit depth (length of longest path(s) from input to output).

A connected graph is a graph that contains a path between any two vertices.

###Challenge

Build a [2-input NAND-gate] circuit that determines whether a 4-vertex graph is connected.
(A gate's 2 inputs can be the same input bit or other gate.)
Output True if the graph is connected, and False otherwise.

###Input

The six possible edges of a simple graph with 4 vertices:

[ ₀e₁ , ₀e₂ , ₁e₂ , ₀e₃ , ₁e₃ , ₂e₃ ​]

where _ae_b represents whether there is an edge between vertices a and b

Connectedness is equivalent to the following conditions:

• If less than 3 inputs are True then output False.

• If more than 3 inputs are True then output True.

• If exactly 3 inputs are True and they form a triangle then output False.

• Otherwise, output True.

The answer that uses the fewest gates wins. ​ Ties will be broken by
the lowest circuit depth (length of longest path(s) from input to output).