# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

48 views

### planarity of trivalent graphs with a cyclic ordering on the edges in each vertex

Let $G$ be an (undirected) trivalent graph. For each vertex $v$ of $G$ we choose a cyclic ordering on the edges coming into $v$ (so if vertex $A$ has neighbors $B, C$ and $D$ we decide whether the ...
20 views

### Matching vertices between two graphs

I have a situation where I have two graphs that are supposed to represent the same underlying topology but represent the underlying topology at different resolutions. My goal is to match vertices ...
35 views

### Prove or dis-prove that it always holds or not $\lambda(G) \leq \chi(G)$ [closed]

I want to prove that this inequality holds or not? The inequality is $\lambda(G) \leq \chi(G)$ where $\lambda(G)$ is the minimum number of edges whose deletion from a graph $G$ disconnects $G$, ...
29 views

### How does the following graph have an Euler tour and not every node has degree that is even?

The theorem states: A connected graph has an Euler tour if and only if every vertex has even degree. But this graph has node 'A' with degree = 3. Graph image. ...
78 views

### Graph theory application of homology

I am struggling with the idea of local homology groups and would like to see an example of how to go about finding them in general. I'm thinking of the most trivial case to apply the theory of local ...
31 views

### How to find List Chromatic Number of planar graphs [closed]

I want to know how we can find the list chromatic number of planar graphs, Suppose we have graph $G= K_{3}$. Then its chromatic number is $3$, but what is the list chromatic number of $K_{3}$? ...
36 views

### Any undirected graph on 9 vertices with minimum degree at least 5 contains a subgraph $K_4$?

Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$. I came up with this question when I were trying to find Ramsey ...
151 views

### A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
30 views

### Number of arcs in undirected graph

It is a basic question in graph theory! I have n nodes and I would like to calculate the number of paths among n nodes so that each node appears once in a path. I think it is Hamilton cycle, but I am ...
20 views

### Number of nodes satisfying a certain property on a binary tree

Fix a large integer $M$ and construct a binary tree as follows. Assign the root node by the integer $0$. If a node is assigned the integer $n$ and $n \leq M - 2$, then $n$ has two children and ...
36 views

### Does the complete graph contain the maximum number of simple cycles?

Let $\mathcal{G}(n,m)$ be the set of connected, simple graphs with $n$ vertices and $m$ edges. For any graph $G$ we denote its number of simple cycles with $\mu(G)$ and and for any finite family of ...
1k views

### counting simple, connected graphs

I've been thinking about this for a few days, but I haven't found a general solution yet. How many distinct simple, connected, undirected graphs are there of n labelled vertices? For example, there is ...
28 views

### Chinese Postman Problem - open walk variation

Consider the following variation of the Chinese postman problem (also known as the route inspection problem). Instead of finding the shortest closed walk which traverses each edge at least once, find ...
151 views

### ER graphs, expected number of triangles incident to one vertex

I'm really sorry for this question. I'm new to a graph theory, and I hope you will help me to understand one statement. Consider $ER(n,p)$ graph with $n \geq 3$ and $p \in [0,1]$. The statement ...
23 views

### Relationship between ST-Path Ideals and ST-Cut Ideals?

Topic: st-connectivity, st-cut ideals and path ideals of a graph My Lemma: None of the st-cut-monomials vanish iff there is at least a st-path that does not vanish. Example ST-cuts: {{1,3,5,6},{...
72 views

### Complete Graph with odd degree

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with odd degree of its ...
55 views

### relationship between uniform Hypergraph maximum matching minimum vertex cover minimum clique partition

A k-$\bf{uniform}$ hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a size $k$ subset of $V$. (Note: ...
24 views

### Is the maximum size of a matching of graph equal to the maximum size of a matching of its dual?

This is really puzzling me! A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$. A ...
30 views

### Proof of Petersons theorem (less than 3 bridges) with Tutte's Theorem

Petersons Theorem: A 3-regular graph with at most 2 bridges has a perfect matching. My task is to prove this theorem by just using Tutte and not Tutte-Berge. My first general question: Are you ...
15 views

### Class of directed graph for which there is only one path to a given parent?

From a nomenclature standpoint, I am wondering if there is a name for a class of directed graph that has only one path to any given parent. I can visualize this shape as an upside down tree that may ...
49 views

### Prove that a graph has a cycle of length no more than $14$

A graph contains $2016$ vertices, its chromatic number is $5$, prove that this graph has a cycle of length $\leq 14$. Where do I start?
12 views

31 views

### If deg$(v) \geq k$ for all $v \in V(G)$, then G contains a matching of cardinality $\min \{k,\lfloor{\frac{|V|}{2}}\rfloor\}$

Let$G = (V; E)$ be an undirected graph. Show that if deg$(v) \geq k$ for all $v \in V$, then G contains a matching of cardinality $\min \{k,\lfloor{\frac{|V|}{2}}\rfloor\}$. I have no idea how to ...
18 views

### Principle of Duality on digraphs: dual properties?

Given an arc $uv$ of a digraph $D$, the dual $D'$ of the digraph $D$ has the arc $vu$. I am trying to find dual properties for digraphs. I could find a page 301 of document on Principle of Duality for ...
18 views

### Duality between cut ideals and cycle ideals?

There exist a general duality between vertex-cuts and cycles and also Duality Principle on Digraphs. I am trying to find a duality prienciple expressed in terms of ideals so Does there exist a ...
2k views

### A cardinality of a graph

If I have graph $G=(V,E)\\$ What is the meaning of $|G|$? (The cardinality of G). I'd like to few words about it... Thank you!
39 views

13 views

### Orient edges in a mixed graph to minimize the critical path

3 down vote favorite A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way ...
317 views

### When a 0-1-matrix with exactly two 1’s on each column and on each row is non-degenerated? [1]

Let $A$ be an $n\times n$ matrix with entries in the set $\{0,1\}$ which has exactly two ones in each column and two ones in each row. Give necessary and sufficient conditions for the rank of $A$ to ...
2k views

### Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: Since the matchings are perfect, each vertex has degree $0$ or $2$ in the symmetric difference, so ...
64 views

### Existence of $K_3$ in a graph with $(n^2+1)$ edges

I was working on this problem for quite a long time and was unable to solve it. Any help will be appreciated. Let $G$ be a graph with $2n$ vertices ($n \in \mathbb{N})$ and $n^2+1$ edges. Show that ...
40 views

### How many distinct directed acyclic graphs are there?

Given $|V|=4$ and $|E|=3$, how many distinct directed acyclic graphs can be formed? Isomorphic graphs should be counted as one. There is one where three periphery nodes point to a central node. ...
16 views

### Demonstration of Cycle-cut duality on elementary graphs?

I want to see examples on the Duality theorem between cycles and cuts on the page 26 of Graph Theory Electronic Edition 2005 by Reinhard Diestel. How to demonstrate the duality theorem between ...
17 views

30 views

### Prove a cube graph has no even walks?

The following question was in my exam, and I didn't even have any idea on how to start, so I'm quite curious to see a proof. I was given a cube graph (the one on the left): The question was as ...
58 views

### Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the ...
19 views

### Adjacency matrix is totally unimodular

Prove that the adjacence matrix of a simple graph is totally unimodular... I know incidence matrices are totally unimodular because in every column there is a 1 and a -1... makes things easier. Any ...
40 views

### L(G) is isomorphic to G iff G is a cycle

The converse is pretty obvious. If G is a cycle, then it is isomorphic to it's line graph. How to prove that if L(G) is isomorphic to G, then G is a cycle...? P.S.- Assume G is connected
56 views

### Find the Eigenvalues of Petersen Graph

Petersen graph is k-regular graph on $n$ vertices and $m$ edges. We can find eigenvalue of $k-regular$ graph by characteristic polynomials of $G$ (denote $\chi_G (x)$) and $L(G)$ (denote $\chi_L (x)$)...
48 views

### What is the expected number of triangles contained in this graph?

I can't seem to understand this question and I really don't know where to start. Could someone please give an explanation as to how to go about answering this? A simple graph is formed randomly on ...
I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
Let us assume we are in the following situation: We have a connected regular locally finite graph $G=(V,E)$ and let us call the degree of an arbitrary (and therefore any) vertex $d$. In addition we ...