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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
0answers
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: \...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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|$.
0
votes
1answer
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 ...
5
votes
2answers
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 ...
-2
votes
0answers
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$
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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!
1
vote
1answer
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 ...
0
votes
0answers
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 (...
6
votes
2answers
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 ...
0
votes
0answers
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.
0
votes
0answers
31 views

How to prove that two probability measures are equal in the described scenario?

Let $(\mathbb{Z}^d, \mathbf{E}^d)$ be a graph with vertex set $\mathbb{Z}^d$ and edge set $\mathbf{E}^d$, such that $\mathbf{E}^d = \{(x, y) \in \mathbb{Z}^d \times \mathbb{Z}^d : \sum_{i = 1}^{d} |...
0
votes
0answers
10 views

Does this definition for cycles in hypergraphs appear anywhere?

I'm looking for a definition of a cycle on a $k$-uniform hypergraph that is equivalent to the following definition: Let $H=(V,E)$ be a $k$-uniform (each hyperedge contains $k$ vertices) hypergraph on $...
1
vote
0answers
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.
0
votes
0answers
29 views

Probability of a vertex not belonging to a set of edges in a random hypergraph.

Let $H(n,p)$ be a $r$-uniform random hypergraph on $n$ vertices, with vertex set $V$ and edge set $E$. Let $E' \subset E$ be a set of edges with some known characteristics, and $V' = V \setminus \{u_i:...
0
votes
0answers
23 views

Can someone explain Woodall's Conjecture?

I am trying to understand this: http://garden.irmacs.sfu.ca/op/woodalls_conjecture But, I am struggling with the definition. Any explanation of "$ k $ disjoint dijoins" for laymen be great. ...
1
vote
0answers
41 views

Scores of black and white marks

We have a connected (undirected) graph with $n$ vertices, and $b$ black and $w$ white marks with $b+w=n$ and $\max(b,w)\geq 2$. In a placement of the marks on the vertices, the "score" of a ...
1
vote
1answer
51 views

Sum related to Goodman's Formula

Suppose I have a (improper) 2-coloring of $E(K_n)$. Define the graph of all red edges to be $G$ and the graph of all blue edges to be $G'$. Then Goodman's formula says that the total number of ...
0
votes
1answer
26 views

In how many ways can you subtract edges from the graph of a cube so that there are no isolated vertices?

Suppose you have a graph with 8 vertices where each vertex is connected to three others, making 12 edges (essentially the graph of a cube). In how many ways can you subtract edges from the graph so ...
0
votes
0answers
48 views

How is the Chebyshev's inequality used in this instance?

I'm looking at the following situation, where the quantity $|E'|$ is estimated, given parameters $\epsilon, \delta_1, n,p, \text{and } r$. $\mathbb{E}\left[\left|E^{\prime}\right|\right]=e(H) p=\left(...
1
vote
1answer
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 ...
4
votes
1answer
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$...
0
votes
2answers
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 ...
0
votes
0answers
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'...
2
votes
2answers
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
1
vote
1answer
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}$. ...
1
vote
1answer
50 views

There exists an $\aleph_0$-coloring of a graph on the real numbers.

I have this question: Let $G = ( \mathbb{R} , E)$ be a graph such that its vertices are the real numbers and its edge set is given by $$E = \big\{ \{u,v\}\,\big |\, u-v \in \mathbb{Q} \setminus \{0 \...
0
votes
1answer
23 views

Isomorphic graphs derived from $K_{10,10}$

How many subgraphs of $K_{10,10}$ exist that are isomorphic to the graph $G$ on the picture? I can think of $P(10,10)$ but I don't think that all of these cases are isomorphic with $G$
4
votes
1answer
35 views

Minimum cost of a connected graph

$G$ is a connected graph with cost $p:E(G)\to\mathbb{R}$ defined on its edges. Let $e' \in E(G)$ be such that $p(e')<p(e)$ for every $e\in E(G)-\{e'\} $. Is it possible to find two spanning trees ...
0
votes
1answer
34 views

Example of a Graph

What is the smallest simple Graph with all but one nodes having degree 3. The last node having degree 2? I have tried looking for relevant Graph Theory books but couldn't find how to proceed.
0
votes
1answer
21 views

Diameter of connected tree emerging from a graph cycle

Let there be a Graph $C$ which is a cycle with $n+1$ vertices. Choose a random vertex $v1$ and add edges until $v1$ is connected with all the other vertices of the cycle. Show that the new Graph $G$ ...
2
votes
0answers
29 views

Proof of $m \leqslant n \times \frac{\sqrt{4n-3} + 1}{4}$ in a graph with no cycle with length 4. (m: edges, n: vertices)

I have faced a problem and do not know how to prove the following. In a graph with no cycles with length $4$, prove that $$m \leqslant n \times \frac{\sqrt{4n-3} + 1}{4}$$ where $m$ is the number of ...
0
votes
1answer
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 ...
0
votes
0answers
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 $ ...
2
votes
2answers
48 views

Did my math textbook make a typo?

My textbook defined connectedness in graphs in the following way: A graph G(V, E) is said to be connected if for every pair of vertices u and v there is a path in G from u to v. The textbook then ...
0
votes
1answer
32 views

Graph theory: Questions about Hamiltonian cycles.

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

1
2 3 4 5
371