Trees and the Matrix Tree Theorem

Question 1

acyclic:

Answer 1

a graph is acyclic if it has no cycles

Question 2

tree:

Answer 2

a connected, acyclic graph

Question 3

forest:

Answer 3

a graph whose connected components are all trees
note - a forest is not a tree, a tree must be connected and a forest cannot be

Question 4

leaf:

Answer 4

a vertex in a tree is a leaf (node) if deg(v)=1
it’s an internal node if deg(v)>=1

Question 5

binary tree:

Answer 5

a tree in which every internal node has deg(v)=3 (2 out, one to lead to it)

Question 6

rooted tree:

Answer 6

a tree with a leaf node that is designated the root node

Question 7

isolated:

Answer 7

a vertex is isolated if it has no neighbours, isn’t connected to anything, deg(v)=0

Question 8

G\v:

Answer 8

the subgraph created from G by deleting the vertex v and all associated edges (incident edges to call them properly)

Question 9

G\e:

Answer 9

the subgraph created from G by deleting the edge e (not any attached vertices, they can stay)

Question 10

a connected graph on n vertices has at least (n-1) edges proof:

Answer 10

base case - |V|=1, |E|=0, all by definition, which fits
hypothesis - suppose it’s true for all graphs G(V,E) with 1<=|V|<=n0, for some fixed n0
induction - consider the connected graph G(V,E) with |V|=n0+1, so we want to reach |E|>=n0. choose any vertex v and create G\v, with vertex set V’=V\v and edge set E’.
if G\v is connected still, then |V’|=|V|-1=n0, hypothesis says then |E’|>=n0-1, but we deleted a vertex that must have been connected to at least one other by an edge cause the G is connected, so |E|>=|E’|+1>=n0-1+1, so |E|>=n0
if G\v is now k>=2 connected components, call them G1(V1,E1),…,Gk(Vk,Ek) with nj=|Vj| (arbitrary number 1<=j<=k)
(k)Σ(j=1)nj=(k)Σ(j=1)|Vj|=|V’|=|V|-1=n0
hypothesis applies to each component so
|E’|=(k)Σ(j=1)|Ej|>=(k)Σ(j=1)(nj-1)>=((k)Σ(j=1)nj)-k>=n0-k
and cause we know G is connected, deleted v must have been connected to k other vertices, so |E|>=|E’|+k>=n0-k+k, so |E|>=n0 as desired

Question 11

an acyclic graph on n vertices has at most (n-1) edges proof:

Answer 11

base case - K1, acyclic with max n-1 edges
hypothesis - suppose it’s true for all acyclic graphs with |V|<=n0 for some fixed n0
induction - consider an acyclic graph G(V,E) with |V|=n0+1, so we want to reach |E|=n0. choose any edge e and delete it to give G\e, which has the same vertex set V but E’=E\e. G\e must have one more connected component than G, as G is acyclic so nothing else can be connecting those 2 vertices. so G\e has k>=2 connected components, G1(V1,E1),…,Gk(Vk,Ek). nj=|Vj|(arbitrary number 1<=j<=k), nj<=n0 for all j so the hypothesis applies to each component, |Ej|<=nj-1
|E’|=(k)Σ(j=1)|Ej|<=(k)Σ(j=1)(nj-1)<=((k)Σ(j=1)nj)-k<=n0+1-k
|E|=|E’|+1<=n0+1-k+1<=n0+2-k<=n0 (cause G’ has k>=2 connected components

Question 12

if a graph G has n>=2 vertices, none of which are isolated, and (n-1) edges, then G has at least 2 vertices for which deg(v)=1 proof:

Answer 12

say the vertices are numbered and arranged in order of increasing degree (so deg(v1)<=deg(v2)<=deg(v3)…)
by the handshaking lemma, (n)Σ(j=1)deg(vj)=2|E|=2(n-1)=2n-2
no vertices are isolated so deg(vj)>=1 for all j
assume, aiming for a contradiction, that there is at most 1 vertex with degree 1
then (n)Σ(j=1)deg(vj)=deg(v1)+(n)Σ(j=2)deg(vj)>=1+(n)Σ(j=2)2>=1+2(n-1)>=2n-1 which is a contradiction

Question 13

prove that any 2 of the following imply the third:
(a) G is connected
(b) G is acyclic
(c) G has n-1 edges

Answer 13

(a) and (b): a connected graph has |E|>=(n-1), an acyclic graph has |E|<=(n-1), so |E| must equal n-1
(a) and (c): assume for a contradiction that you can have a connected graph with n-1 edges and a cycle. choose some edge e and delete it for G\e. G is then still connected, and has n-2 edges, which is a contradiction.
(b) and (c): base case - |V|=1, it’s acyclic, |E|=n-1, and it’s connected by definition
hypothesis - suppose all acyclic graphs with 1<=|V|<=n0 vertices and |E|=|V|-1 edges are connected
induction - consider an acyclic graph G(V,E) with |V|=n0+1 and |E|=n0. such a graph cannot have any isolated vertices cause then we could delete it to have a graph with |V|=n0 and |E|=n0 which is a contradiction. therefore, it has at least 2 vertices of degree 1. take one of these and delete it for G\v=G’(V’,E’). G’ is still acyclic cause deleting stuff can’t create a cycle, and |V’|=|V|-1=n0 vertices and |E’|=|E|-1=n0-1 edges. this means the hypothesis applies so it’s connected, and cause G’ is connected, G must also be

Question 14

spanning tree:

Answer 14

a subgraph of G(V,E) that is a tree that contains every vertex in V (but not necessarily all edges)

Question 15

graph laplacian:

Answer 15

a matrix where Lij=deg(vj) if vi=vj, -1 if vi!=vj and (vi,vj) is an edge, and 0 otherwise
alternatively, L=the matrix where the diagonal is the degree of that vertex - the adjacency matrix

Question 16

kirchoff’s matrix-tree theorem:

Answer 16

if G(V,E) is an undirected graph with graph laplacian L, then the number NT of spanning trees contained in G is given by taking L, removing some vertex (one row and one column) and computing the determinant of that matrix

Question 17

root:

Answer 17

a vertex v in a digraph is a root if every other vertex is accessible from v

Question 18

arborescence:

Answer 18

a digraph is an arborescence (or directed tree) if it contains a root and the graph obtained by ignoring direction of edges is a tree

Question 19

spanning arborescence:

Answer 19

a subgraph that’s an arborescence that contains all vertices of G

Question 20

tutte’s matrix-tree theorem:

Answer 20

kirchoffs but for digraphs
if G(V,E) is an undirected graph and L is a matrix with Lij=deg(in)(vj) if vi=vj, -1 if vi!=vj and (vi,vj) is an edge, and 0 otherwise, then the number NT of spanning arborescences with root vj is given by taking L, removing vj’s row and column and computing the determinant of that matrix

Question 21

fix(a) of a permutation:

Answer 21

{j|a(j)=j} - where it’s the same before and after permutation

Question 22

symmetric group:

Answer 22

Sn
the identity element is the permutation for which a(j)=j for all j in the set
Sn has n! elements

Question 23

cycle (permutation):

Answer 23

a permutation a specified by a sequence of distinct integers such that a(j)=j if j isn’t in the sequence, a(i(j))=i(j+1) for 1<=j<l (l being the length of the sequence), and a(i(l))=i(1)
brackets after i are subscript

Question 24

transposition:

Answer 24

a cycle (permutation) with l=2

Question 25

sign of a permutation:

Answer 25

sgn: Sn -> ±1
if a is the identity permutation, sgn(a)=1
if a is a cycle of length l, sgn(a)=(-1)^(l-1)
if a has a decomposition into k>=2 disjoint cycles with lengths l1,..,lk, sgn(a)=-1^(L-k) where L=(k)Σ(j=1)lj
all that’s the same as saying sgn(a)=1 if a is the product of an even number of transpositions, -1 otherwise

Question 26

Ga:

Answer 26

a is a permutation
V={1,…,n}
E={j,a(j)|j in V and a(j)!=j}

Question 27

the cycle (i1,…,il) appears in the cycle decomposition of a iff:

Answer 27

the directed cycle defined by the vertex sequence (i1,…,il,i1) is a subgraph of Ga

Question 28

inclusion/exclusion:

Answer 28

|X1∪X2|=|X1|+|X2|-|X1∩X2|

Question 29

spreg:

Answer 29

a single predecessor graph is a subgraph T(V,E’) of digraph G(V,E) with distinguished vertex v in which each vertex has exactly one predeccesor except v, which has 0
note that the vertex set is the same and that the graph need not be connected, as long as there’s only one v and everything else has 1 predeccesor

Question 30

spanning arborescences with root v are spregs with distinguished vertex v proof:

Answer 30

the vertex set is the same by definition
we are checking all the vertices that aren’t the distinguished vertex have exactly 1 predecessor and that there is a distinguished one, v, that has 0
assume for a contradiction that deg(in)(v)>0
therefore T must include a directed cycle - consider the predecessor of v, u0 - it’s accessible from v, so there must be a directed path from v to u0, which means a path from v to v, which contradicts T’s definition as an arborescence, so deg(in)(v)=0
assume for a contradiction that there exists some vertex u such that deg(in)(u)>=2. take two predecessors v1 and v2, noting that one could be v. consider the paths from v to v1 and v2. this shows that there must be a cycle, which contradicts T being an arborescence

Question 31

characterising spregs:

Answer 31

a spreg with distinguished vertex v consists of an arborescence rooted at v plus 0 or more disjoint weakly connected components, each of which contains a single directed cycle. proof is similar to the proof that spanning arborescences with root v are spregs with distinguished v