# Questions tagged [graph-theory]

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.

18,543 questions
Filter by
Sorted by
Tagged with
6 views

### Do all claw-free, even-hole-free graphs contain a simplicial clique?

A claw free graph is a graph that contains no claws. An even-hole-free graph is a graph that contains no cycles with an even number of vertices. A simplicial clique in G is a non-empty clique K such ...
32 views

### Is this conjecture regarding simple graphs obvious?

Given a simple directed graph such that no node is a sink node i.e. each node has at least one outgoing edge. Let the minimum outgoing edges for any node ($O_{min} = K; K>0$). We can always remove ...
17 views

### Smallest $k$ to make sure the $k$-nearest-neighbor graph is connected

Given any $n$ points in $\mathbb{R}^d$, then make an undirected edge between every point and each of its $k$ nearest neighbors (in Euclidean distance). What is the smallest $k$ to make sure that the ...
17 views

### Matchings in bipartite graph

I was given the following statement: Be $G=(X \cup Y, E)$ a bipartite graph connected with $|X|=|Y|=4$ $|E|=7$ , all maximal matching in G is maximum. I must say if it is true or false and justify. By ...
10 views

### Graph proving a cycle inequality

I was solving some old exams from my university and I've stumbled across this one which I didn't know how tto think through, it says: Give a graph H. Let u(H) be the number of vertices of H of degree ...
11 views

### Cycle graph of the symmetry group of a 4D hypercube

I suspect this may be a question about software tools or reference materials as much as it is about math. What's a reasonable way for me to obtain a picture of the cycle graph of the symmetry group of ...
34 views

### Uniqueness of the solution of a linear system involving the graph Laplacian

Let $L$ be a Laplacian matrix of a connected graph $G = (V, E)$ and $D$ its degree matrix. Then, for a vector $z \in \mathbb{R}^{|V|}$ and a constant $\rho \in \mathbb{R}$, I have the following: \...
21 views

### Topologies for graphs

Some of the basic definitions in Graph theory made me wonder if there is by any chance a way to give a graph $G$ a topology, such that these definitions can be understood as versions of analogous ...
11 views

### Notion of distance in a Hypergraph

I've been trying to find canonical notions of distance in hypergraphs which generalize the notion of distance in graphs. I was hoping for a distance which also encodes a metric on two subsets of the ...
15 views

### Tighter bound for the total number of possible $m$-ary tree with $n$ nodes and maximum height $h$?

I know that the total number of possible $m$-ary tree with $n$ nodes is \begin{align} C_n&=\frac{1}{(m-1)n+1}{mn \choose n}, \end{align} which is the Catalan number. I want to know if I can get a ...
43 views

### Tournament plan

Last week, my math teachers and I were asked to solve a problem for a gym teacher. He has 12 sprinters and 3 lanes to run on. The problem is: How many runs do he has to do to guarentee that each ...
20 views

### Classes of nodes given by graph automorphisms

I've been trying to formalise the following idea in graphs: I want to say that two nodes are "similar" if the rest of the graph looks the same from their point of view. For example, in a ...
34 views

### Proof of graph theorem

Be $G=(V,E)$ single graph, no loops and connected. Prove that G has exactly one cycle if and only if $|V|=|E|$.
28 views

### Proof checking: Graph Theory

Question: Prove that if the number of vertices in graph $G$ is $n \geq 2$ and the sum of $2$ degrees is at least $n - 2$, then graph $G$ has $2$ disjoint simple paths that their union completes the ...
134 views

### How to construct a 5-regular graph with diameter 2 on 22 vertices?

I would like to get a $5$-regular graph with diameter $2$ on $22$ vertices. I know that there are 5-regular graphs with diameter 2 on 20 vertices and also on 24 vertices. The one on 24 vertices can be ...
13 views

### What is the minimum number of edges in N vertices graph contains $C_4$ but not $K_3$

I am looking for the lower bound of the number edges for any graph contains $C_4$ but not $K_3$
100 views

### Algorithm to find the chromatic number of a graph (its not greedy)!!

I have thought of an algorithm to find the chromatic number of a graph but I don't know whether it's right or not. Could someone confirm this for me? So it works like this: Suppose we take the graph ...
7 views

### Measures to compare connected graphs of same vertices?

I have connected graphs, each with the same N vertices. Each graph contains edges connecting the vertices to their nearest neighbor, as determined by a distance function. A different distance function ...
29 views

### connected bipartite graph exists

Does a connected bipartite graph $G=(X \cup Y; E)$ such that $|X|=4$, $|Y|=3$, $|E|=5$ exist? Is there a way to know? Thanks!
53 views

### Do sparse graphs contain regular pairs?

A corollary of the Szemeredi Regularity Lemma says that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. Could one make ...
23 views

### Q: Proving it's the shortest path

Let $T$ be a $G$-generating tree obtained with the wide search algorithm, with r the root. Prove that if $x ∈ V(G)$, the length of the path $r-x$ contained in $T$ is the length of the shortest path (...
720 views

### Can a graph be non-planar in 3d?

I am currently reading Trudeau's introductory book on Graph Theory and have just come across the concept of planar and non-planar graphs. The definition reads: 'A graph is planar if it is isomorphic ...
26 views

### matching perfect - matematics discrete [closed]

Let $G$ be a bipartite network with bipartition $(V_1, V_2)$ such that $|V_1| = |V_2|$. Prove that if $|\operatorname{NG}(U)| \le 2|V_1| - |U|, \forall U \subset V_1$, then $G$ has a perfect matching.
31 views

31 views

### Why is chromatic number of empty graph equal 1

Why is chromatic number of empty graph 1? It seems more natural if it was 0 instead.
29 views

22 views

### Cover and fractional covers

I have troubles understanding this definition of a fractional cover. It was in the context of graphs and random variables. The $1_V$ stands for the indicator function: Let $V$ be a finite set and let ...
43 views

### Q: Proving G is d-colorable

I'm studying graph theory, coloring at the moment. I'm stuck with a proof of the following exercise: Let $G = (V, E)$ be a connected graph and let $v \in V$ be such that $deg(v)\lt d$. If $deg(w)\le d$...
43 views

### Discrete math: If G is a regular graph. What is the degree of each vertex?

strong text Hi, I have a question about discreet math, and the motto goes like this: For each $n \in N$ such as $n ≥ 3$, let's call $X_{n}:={1,2, ..., n}$. We define the simple graph $G_{n}$ as ...
28 views

### Formula for Nodes in a Tree

I am reading section 1.5.2 in this book where they claim that for a tree with branch factor $b$, the number of nodes at distance $R$ from the root is given by $$N(R)=(b+1)b^{R-1}$$ However, I just don'...
40 views

### For $n$ points on a plane, prove that there are at most $3n$ pairs of vertices with distance 1

Question: Given $n$ points in a plane, the distance between any $2$ vertices is at least $1$. Prove there are at most $3n$ pairs of points with distance of exactly $1$. I've seen this thread, which ...
39 views

### Graph Theory: Question about union of 2 Paths

Q: Prove that if a graph $G$ has $n \geq 2$ vertices, and the sum of the degrees of 2 different vertices is at least $n-2$ (for any 2 different vertices), then the graph has 2 disjoint simple paths, ...
49 views

### Application of a lemma to prove Pippenger's 1989 Theorem.

This is a quite involved question so I'd be happy just to be shown how to understand some small parts. I'm trying to read these slides, in which the lemma in slide 25 is used to prove Pippenger's ...
54 views

### Do we have a formula to determine number of cycles in a complete graph? [duplicate]

I just read the formula to determining the no. of paths of length $m$. It was $\frac{n(n-1)\cdots(n-m)}{2}$ Do we have something for cycles too?I think it should be $\frac{n(n-1)\cdots (n-m+1)}{2}$. ...
50 views

41 views

### Graph Theory - Prove complement graph has a diameter of at most $3$ [duplicate]

Given a graph $G$ with a diameter of at least 3. Prove that the diameter of $\bar{G}$ (Complement graph) is at most 3. I got stuck at the very beginning.. why those specific numbers? I mean, I would ...
34 views

### Graph coloring: general question

Assume we have a graph $G=\langle V,E\rangle$ and there exists a coloring $f\colon V \to A$ for a set $A$ such that $|A| = \alpha$. Is it true that for any set $B$ such that $|B|=\alpha$ ...
Prove that if graph $G$ has $n \geq 2$ vertices such that the sum of the degrees of $2$ different vertices is at least $n- 2$, so there are $2$ different simple paths ('foreign' to one another) such ...