Graph theory Flashcards

Question

For a odd number of vertices. What do we know abou the PMP?

Answer 1

PMP = Ø. There exists no perfect matching in a graph with odd number of vertices.

Answer 2

∂(U), for edges between the set U⊆V and V\U.

Answer 3

x_e ≥0, x(∂({v}))=1 ∀v∈V x(∂(W))≥1∀ W⊆V with |W| odd

Answer 4

A matroid is a mathematical structure that generalizes the idea of independence, like linearly independent vectors, and applies it to different areas, including graphs. In graph theory, a matroid focuses on edges, where a set of edges is "independent" if it doesn’t form a cycle. This ties to concepts like forests and spanning trees. Matroids are useful because they unify and simplify problems. In graphs, they help with things like efficiently finding spanning trees, and they connect graph theory to other fields like optimization and combinatorics.

Answer 5

A subgraph that does not contain a cycle.

Answer 6

An independent subgraph is a tree and can at most have n-1 edges for n vertices. Meaning if we add one more edge to the spanning tree, we create a cycle, and it is not independent anymore.

Answer 7

A graph is planar if we can draw it in R^2 with edges only overlapping at vertices. K_4 is planar but K_5 is not. (can easily bee proofed)

Answer 8

A way of drawing a graph in the 2-dimensional plane such that it is planar. K_4 has two embeddings in the plane.

Answer 9

The dual graph G^* have a vertex for each face in G and an edge for each edge in G that separate faces.

Answer 10

Deletion is deleting an edge but not changing the number of vertices. The number of edges decreases by one and the number of faces decreases (unless the same face is on both side of the edge) Contraction is removing an edge and identify the two vertices connected to that edge into one (big) vertex. Both the number of vertices and edges decreases by one. (unless the edge is a loop) G->deletion -> dual = G-> Dual -> contraction Deletion on a graph corresponds to doing a contraction on the dual.

Answer 11

Two graphs are isomorphic if their structure are identical. They have the same vertices and edges but are represented differently.

Answer 12

Matroid as a pair, M=(E,I) with ground set E and I a set of independence subsets of E. A subset I of E is independent if: Ø∈I If A∈I and B⊆A, then B∈I If A,B∈ I and |B|<|A|, then ∃a∈A\B s.t. B∪{a}∈I

Answer 13

A set I of subsets of the ground set E, where elements of I are linear independent. For a graphic matroid it means the elements doesn’t form a cycle in the graph.

Answer 14

A basis of a matroid M=(E,I) is a subset B⊆E s.t B∈ \scriptI and B is not a subset of any other set of \scriptI.

Answer 15

Assume |B|=|B'| +1. Use axiom I3

Answer 16

the size of any basis

Answer 17

Matroids arising from graphs. Subsets of E corresponds to spanning subgraphs of G. I is the set of subgraphs that does not contain a cycle. The pair (E,I) is called the cycle matroid of G.

Answer 18

The edge set of a cycle in the graph. It is the minimal dependence set. The set of all circuits is denoted C(M)

Answer 19

For a bipartite graph G[X,Y] the transversal matroid of G is the pair (X,I) where I≔{I⊆X:∃a matching M:I is the set of vertices of X covered by M}

Answer 20

For a matroid M=(S,I). The set B of bases of M satisfies: 1. B≠Ø and no element from B is a subset of another element of B (they all have the same size to be a basis) 2. If B_1,B_2∈B and x∈B_1, then there exists y∈B_2 s.t. (B_1\{x})∪{y}∈B The bases of a graphic matroid are the spanning tree in the graph.

Answer 21

For e∈S, e is a loop if it’s not contained in any basis of M e is a coloop if it’s contained in every basis of M

Answer 22

In a directed graph with weight function. A subset B⊆E is called a branching if B contains no cycles Each vertex has at most on in-going arc from B An optimum branching is a branching of maximal weight. (this is not the max-weight spanning tree of the undirected graph since we might not be able to add an edge in the branching because of its direction. In a tree, there is no directions.)

Answer 23

An arc e∈ E is called critical if w(e)>0 and for every other arc e^'∈E with the same head as e we have w(e)≥w(e'). So, for each v∈V, choose the arc with highest weight. (Critical arcs are priories in finding optimal branching. By focusing on critical arcs we avoid unnecessary computations with arcs that are not essential.) We might still need non-critical arc to form an optimal branching.

Answer 24

A subgraph H⊆E is called critical if Each arc of H is critical No two arcs in H have the same head OBS: H is allowed to have cycles. Branchings are not allowed to have cycles.

Answer 25

then it is an optimum branching. It is a branching because it has no cycles by assumption and it is a critical subgraph (definition). It is optimal since it chooses the largest weight in-going arc for each vertex.

Answer 26

This is because every cycle only has one direction. Since no arc can share one head. So these to cycles must be equal/the same

Answer 27

It simply says that in a maximal critical subgraph H, we can achieve the optimal branching 𝐵 by removing on edge from 𝐶𝑖. There is only 1 arc in different between the subgraph 𝐻 and the branching 𝐵 (for each cycle) Intuition: Just show that no arcs in 𝐻\𝐵 is eligible, meaning there is no arc from the max critical subgraph that is not a part of the branching, we can add and still have a valid branching. By contradiction assume 𝑒 is eligible. Then we get one more arc from 𝐻. (And the arc we replace was not a part of H since they share head and H is critical and contains 𝑒.) Adding this arc did not lower the total weight since the arc is critical. So, we have added an arc from H and increased our branching which contradict that B was optimal from the beginning. So, there is no eligible edge.

Answer 28

Assign new weight to all edges in G\C that has its head in one u_i: w^' (e)=w(e)-w(e ̃ )+w(e_i^0 ) where e ̃ is the edge in C_i that shares head with e. and e_i^0 is the edge in C_i with the smallest weight.

Answer 29

w(B)-w'(B') = ∑_(i=1)^k w(C_i ) - ∑_(i=1)^k w(e_i^0 )

Answer 30

For a branching B in G=(V,E), and edge/arc e=(x,y)∈E\B that is not in the branching and for an arc e^'∈B with head(e^' )=y, then B\{e'}∪{e} is a valid branching, then e is called eligible.

Answer 31

Intuition: B\\{e'}∪{e} cant be a valid branching if there exists a (y,x)-path since it will create a cycle and then e is not eligible

Answer 32

By k-vertex coloring of G we mean a function c:V→C where C being a set of “colours” and |C|=k. A graph is k-vertex colourable if there exists a proper k-vertex colouring of G.

Answer 33

For vertices: If ∀e=(u,v)∈E we have c(u)≠c(v) For edges: ∀v∈V the edges incident to v have different colours. (Require G to have no loops)

Answer 34

(Vertex) chromatic number: χ(G), smallet number k such that G is colourable. (there exists a proper colouring) (Edge) chromatic number: χ'(G), smallet number k such that G is k-edge colourable. Δ: Defines maximal degree of any vertex, Δ=max(v∈V)⁡〖deg⁡(v)〗

Answer 35

Since every vertex has at most Δ neighbors.

Answer 36

Every graph that is not cycle or a complete graph is Δ-colourable. (is trivial)

Answer 37

Is a polynomial function P(G,λ) that tells us the number of proper colourings of a graph G using λ colours.

Answer 38

λ^n (because for each vertex we can choose it colour freely)

Answer 39

K_n: λ!/(λ-n)!, P(K_n,λ)=λ(λ-1)(λ-2)·…·(λ-(n-1))

Answer 40

λ·(λ-1)^(n-1)

Answer 41

P(G,λ)=P(G+e,λ) + P(G*e,λ)

Answer 42

Tait proof the 4-colouring theorem by proving that “Every 3-connected planar cubic graph G has a Hamiltonian cycle. “ This was disproved by Tutte by a counterexample of a graph that is 3-connected planar cubic, but does not contain a Hamiltonian cycle.

Answer 43

It is a graph where every vertex has degree three. The complete bipartite graph with |X|=|Y|=3 is cubic.

Answer 44

It is a graph with more than 3 vertices and remains connected whenever fewer that 3 vertices are removed.

Answer 45

Hamiltonian cycle is a path/cycle in a graph that visits each vertex exactly once.

Answer 46

We are able to make a proper colouring of every graph with only 5 colours.

Answer 47

Since the graph is bipartite, there is not edges between vertices in the same set. Re always have that only vertices in X are red while vertices of Y is blue. It is never possible to have different color vertices in the same set.

Answer 48

Deletion doesn't change the rank of M Contraction decreases the rank by 1.

Answer 49

In a bipartite graph G has a matching, matching all vertices of X if and only if: For all subsets S of X, |N(S)|≥|S| S need to have at least a many neighbors has its size such that for ever x in S you have at least one neighbor you can match it to.

Answer 50

A matroid from a bipartite graph, M=(X, \scriptI ). The independents sets is a set of subsets I of X, where there exists a matching M: I is the set of vertices covered by M

Answer 51

Check 3 axioms.

Answer 52

M: B, M*: S\B

Answer 53

PMP describes all perfect matchings in a loop-free graph and express the set as a polytope (convex set) PMP(G) consists of vectors that corresponds to perfect matchings: Characteristic vector: X_M \in R^E. Indicates whether an edge e is in the matching M PMP is the convex hull of all characteristic vectors of all perfect matchings: PMP(G)= conv({X_M : M is a perfect matching})