# 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.

1answer
36 views

### Show that $C_n\times K_2$ is $1$-factorable for $n\ge4$

Show that $C_n\times K_2$ is $1$-factorable (has a perfect matching) for $n\ge4.$ $\times$ means the Cartesian product. $C_n$ means a cycle where $n=$ number of vertices of the cycle. $K_2$ means the ...
3answers
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 ...
3answers
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 ...
0answers
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 ...
1answer
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}$? ...
0answers
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 ...
1answer
40 views

### Neighbourhood set in Graph theory [closed]

Let $G$ be any connected graph with $\Delta(G)$ be maximum degree. If $D \subseteq V(G)$ then how can we say that $\left | \bigcup \limits_{v \in D} N(v) \right | \leq |D| \Delta(G)$.
1answer
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 ...
0answers
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},{...
0answers
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: ...
1answer
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 ...
0answers
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 ...
0answers
12 views

### Acyclic orientation of a mixed graph with minimization of the critical path

I already asked this question as a guest but I was not able to edit it or add comments after I registered with my e-mail address. A apologize for asking the same question again. A mixed graph is a ...
1answer
49 views

### Find number of vertices when given number of edges

A Simple Connected Graph G has $M$ vertices and 4 edges, find $M$ Now lets say we didn't have any more info than what's mentioned above. By drawing out a couple of graphs I know that $M$ could ...
1answer
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 ...
1answer
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 ...
2answers
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?
0answers
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 ...
0answers
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 ...
0answers
39 views

0answers
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 ...
0answers
34 views

### Paths in a linear graph

Is there an expression for the number of paths of length $k$ from one end of a linear graph of length $N$ to the other?
1answer
53 views

### Infinite resistor problem from a graph theory standpoint

I am trying to understand the infinite grid of resistors problem from a graph theory stand point(classic xkcd/google problem). Since effective resistance is the same as the commute time, this is ...
2answers
33 views

### Graph's Matching and edge covering

Let $G$ be a graph and $M$ a match with maximum size and $F$ an edge cover with minimal size. Prove that: $|M|+|F| = |V|$ That means that the number of all Matches with maximum size and the number of ...
1answer
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. ...
1answer
65 views

### proof of Triangle Removal Lemma

Where can I find a proof of the following version of Triangle Removal Lemma (or any version equal to it)? Let $G(V,E)$ be a graph on $n$ vertices such that it contains $\varepsilon n^3$ triangles, ...
0answers
98 views

### Integral identity graphs — smallest example

From Paulus Graphs. "The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs (or asymmetric) and identity graphs (a graph spectrum ...
0answers
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)$)...
1answer
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 ...
0answers
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$ ...
1answer
27 views

### Finding a recurrence for number of paths in a certain tree

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 ...
2answers
30 views

2answers
27 views

### Calculate order of a graph from size of graph and size if its complementary.

Given the order of a graph (without loops) n, which size is 56. And its complementary graph which size is 80. How to find out the value of n?
1answer
39 views

### Uniqueness of graph neighbourhood sizes

I was thinking about graphs the other day, and had the following questions which I suppose fall under the topic of graph reconstruction. I am not very familiar with the literature, so in case this ...
0answers
15 views

### Corona of two graphs and Cartesian product of two graphs

I would like to know whether corona of two graphs is defined for two graphs with disjoint vertex set?? Also I would like to know whether Products of of two graphs (Cartesian, tensor,strong, ...
0answers
23 views

### Implicitization Problem on Graphs?

I learnt the implicitization problem for varieties in introduction course on Algebraic Geometry. I am trying to understand how to formulate a similar implicitization problem on graphs where the ...
0answers
24 views

### Arc-bases and Point-bases: when are they different for finite digraphs?

Definitions Given a digraph $D=(X,U)$, a point-basis of a digraph $D$ is a minimal vertex set from which a dipath exist to every vertex in $D$. An arc-basis is a minimal arc-reaching set. A subset ...