MathDB

no of orientations of a connected 3 -regular graph on 2n vertices

Source: 2020 Dürer Math Competition Finals E+ 1. 5

November 30, 2020

combinatoricsgraph theorygraph

Problem Statement

Prove that the number of orientations of a connected

3

-regular graph on

2n

vertices where the number of vertices with indegree

0

and outdegree

0

are equal, is exactly

2^{n+1}

{2n} \choose {n}