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.

learn more… | top users | synonyms

1
vote
0answers
6 views

possible embeddings for a $2$-connected planar graph

When I asked the question "cycles and faces in planar graphs", I learned that the numbers of vertices in the faces are not unique, if the planar graph is only $2$-connected. My question now is : How ...
0
votes
0answers
5 views

Examples of sequences of graphs with different order of Cheeger constant and spectral gap

According to Cheeger's inequality, the bottleneck ratio/Cheeger ratio $\Phi_*$ of a graph and the spectral gap $\lambda$ of its adjacency matrix satisfies $$\Phi_*^2/2 \leq \lambda \leq 2\Phi_*. $$ ...
1
vote
2answers
13 views

How can I prove that a graph with a required amount of edges per node is invalid?

For the following example I assume that no node may be connected to itself. Nodes: A, B, C, ...
0
votes
1answer
16 views

(Can this be done in polynomial time?)Proving two graphs are isomorphic - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since they all have degree $3$(and ...
0
votes
0answers
19 views

Does $\beta(G)=\alpha'(G)$ always?

Does there exist a graph where the minimum vertex cover does not equal the size of the maximum matching? I'm thinking that if it does, then it cannot be a bipartite graph and so it contains an odd ...
0
votes
0answers
11 views

Markov chains: identifying a nonregular transitional matrix

I am currently TA'ing for a course in which the students are soon to learn about Markov chains and stochastic matrices. During the sections, it refers to the possible existence of a stable state and ...
-1
votes
1answer
12 views

Graph theory problems about vertices and interior angles.

I have three problems of graph theory: $1.$We have a $10$ gon then maximum number of acute angles that we can make is? $2.$We have $5$ vertices then how many connected trees we can make? $3.$How ...
-2
votes
0answers
20 views

Number of triangles in a graph and its complement

Let $G$ be a simple graph with $|V(G)|=n$ and $|E(G)|=e$. let $T$ be the number of triangles in $G$. Show that $T ≥\frac{4e}{3n}(e-\frac{n^2}4)$ and find a larger possible lower bound for ...
0
votes
2answers
17 views

A simple problem of graph theory about the degree of vertices.

A graph has $7$ vertices and $10$ edges then which is true? $(I).3$ vertices of degree $4$ and $4$ vertices of degree $2$. $(II).2$ vertices of degree $5$ and $5$ vertices degree $2$. $(III).$Every ...
0
votes
1answer
19 views

$3$-connected non-hamiltonian graph with at most $3$ independent vertices

Is there a $3$-connected non-hamiltonian graph with at most $3$ independent vertices ? I checked the graphs upto $9$ vertices and the cubic graphs upto $18$ vertices and did not find such a graph. ...
3
votes
1answer
20 views

Find maximum number of nodes in a regular graph of degree 4 and diameter 2

In $n$ nodes directed graph, every vertex has in-degree and out-degree equal to $4$. If every vertex is reachable from every other vertex directed by a path of length at most $2$. How can we find ...
1
vote
0answers
17 views

Mapping graphs to themselves, e.g. the meta-graph

I'm looking for any prior work on a (for lack of a better word) meta-graph. Let $M=(V,E)$ be a a meta-graph with vertex and edge set $V,E$. The meta-graph is formed by mapping a set of graphs $G = ...
0
votes
1answer
19 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
0
votes
4answers
52 views

Prove that $G$ has at least $q-p+c$ cycles.

I need your help with this question: Suppose that a graph $G$ has $p$ vertices, $q$ edges, and $c$ components. Prove that $G$ has at least $q-p+c$ cycles. I don't know how to prove that.
0
votes
0answers
17 views

Breaking Ties Alphabetically Using Kruskal's Algorithm

Kruskal's Algorithm picks the next edge simply by picking the lightest edge. Doesn't that make breaking ties alphabetically impossible? If I had a graph where two edges ...
1
vote
2answers
54 views

Proving that every connected graph has a vertex whose removal will not disconnect the graph.

I have not done much proofs before this and need some guidance. I know that for a simple graph such as this : node - node - node -node Removing the first and ...
1
vote
0answers
9 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
2
votes
1answer
54 views

Are “almost all” graphs hamiltonian?

Let $$p(n):=\frac{\text{number of hamiltonian graphs with $n$ nodes}}{\text{number of graphs with $n$ nodes}}$$ Since $883156024$ of the $1018997864$ graphs with $11$ nodes are hamiltonian, we have ...
0
votes
1answer
16 views

decomposition of graph to cycle and cut space

Let $G$ be a graph. I want to show that $E(G)$ is disjoint union $C\cup D$ where $C$ and $D$ belong to cycle and cut space respectively.
0
votes
1answer
11 views

Extremal graph theory

Determine ex(n,2K2) for every n. (2K2 means a pair of vertex-disjoint edges, ex(n,H) = max{e(G): |G| = n is H-free}) I think the answer might be n+1 choose 2 but I am stuck on where to start.
0
votes
1answer
13 views

Graph Theory (Vertex Connectivity)

Show that for any edge $e\in E(G)$, $κ(G−e)\geκ(G)−1$. ($e$ is an element of the edge set, $κ(G)$ is vertex connectivity) I think this follows from Mengers theorem, but I am having trouble seeing ...
5
votes
1answer
40 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
0
votes
1answer
22 views

Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$. $\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping ...
0
votes
2answers
20 views

If $G$ is simple, then $\epsilon \leq {v \choose 2}$ - Bondy/Murty - Graph Theory with Applications Page 4

Question: Does this proof hold? Is this a bad proof? Any nicer proofs that don't rely on other theorems? Notation: $\epsilon$ - Number of edges $v$ - Number of vertices G - Here, any Graph ...
0
votes
0answers
23 views

Problems in extremal graph theory [on hold]

Determine ex(n, 2K2) for every n. (Here 2K2 means a pair of vertex-disjoint edges).
-1
votes
0answers
21 views

Graph Theory - Paths

A Θ-graph is a graph consisting of two vertices x and y joined by three paths that share no vertices other than x and y. Prove that any Θ-graph contains an even cycle
0
votes
0answers
16 views

Conjecture: If S = P-1 then (P*(P-1)^S -2)/(P-2) is the least upper bound of N.

Given a point to point computer network where each node has $P$ ports. Let $N$, with optimum wiring, equal the number of nodes can be reached in $S$ transmissions or (skips). Using binomial expansion ...
-4
votes
0answers
35 views

SELF COMPLEMENTARY GRPAHS [on hold]

A simple graph is called self-complementary if it is isomorphic to its own complement. Let G be a simple graph on n vertices. Prove that if G is self-complementary, then either n = 4t or n = 4t + 1 ...
5
votes
1answer
75 views
+50

Number of $K_{10}$ always increases

Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any extra edge to $G$, the number of complete graph $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$. [Source: The ...
0
votes
1answer
23 views

Dimension of cut space

Quoting from Algebraic graph theory by Biggs: If $G$ is a directed graph, then the dimension of cut space is rank of incidence matrix of $G$. Now, my question is: What happens when $G$ is not ...
1
vote
1answer
44 views

Proportion of asymmetric graphs

Wikipedia states, that the proportion $$p(n):=\frac{number\ of \ asymmetric \ graphs \ with\ n\ nodes}{number\ of\ graphs\ with \ n\ nodes}$$ satisfies $$\lim_{n->\infty }p(n)=1$$ I wonder ...
1
vote
0answers
29 views
+50

Partition in graph connecting itself and other half

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq ...
0
votes
2answers
18 views

Is the path between 2 vertices of a Minimum weight tree of a graph the shortest path between those 2 vertices?

Suppose we have an undirected, connected graph, $G_1$ If you have a minimum weight spanning tree $G_2$ for graph $G_1$. Is it possible to find two vertices in $G_1$ which is has a shortest path that ...
0
votes
1answer
19 views

Paths of Nearest Neighbours

I'm working on a project about sampling points, where the next point to be added to sample is the closest point to the current point. Furthermore, each point can only appear once in the sample. ...
-2
votes
0answers
22 views

count minimum spanning tree [on hold]

if there is no three edges have the same length in a graph (but two edges can have the same length). How many di efferent MSTs can you have in the worst case? Give an example to show that How fast ...
1
vote
1answer
58 views

Graph of all sets

Working with set theory of ZFC, would it be possible to construct a graph (as in graph theory) with the class of all sets as its nodes? With "is it possible" I mean, would it lead to a contradiction ...
0
votes
0answers
28 views

Spreading a rumour to at least x people with a minimum probability p

I have the following problem: Consider an undirected weighted graph G where the weight of an edge between nodes a and b represents the probability of a message being passed from node a to node b (or ...
0
votes
1answer
37 views

Soundness of a simple tree edge count proof by induction

I'm trying practice and get better at proofs. Here is my attempt at a proof of the following simple statement: There are $n-1$ edges in a $n$ vertex tree. We will prove this by induction on $n$ ...
2
votes
1answer
13 views

show that if $T$ is a tree containing at least one vertex of degree $2$ then $\overline T$ is not Eulerian.

show that if $T$ is a tree containing at least one vertex of degree $2$ then $\overline T$ is not Eulerian. I know that every tree has at least 2 leaves, so they can't be Eulerian. So in $\overline ...
-2
votes
0answers
54 views

Is it possible for everyone to be happy? [on hold]

"everybody is happy" which means that I am happy if the avarage of my friends` income is equal to or less than my income and you're happy if the avarage of your friends' income is equal to or less ...
1
vote
0answers
24 views

Least number $k$ , such there is no graph with $n$ nodes and $k$ hamilton-cycles

Let $f(n):=$min{ $ k \in N$: There is no graph with $n$ nodes and $k$ hamilton-cycles} for $n\ge 3$ The values I found out so far : $$f(3)=2$$ $$f(4)=2$$ $$f(5)=3$$ $$f(6)=9$$ $$f(7)=13$$ ...
0
votes
0answers
33 views

Method for finding bridges and articulation points using DFS

How can we find all bridges and articulation points using DFS? Suppose we have the following DFS psuedocode (from Wikipedia): ...
0
votes
0answers
30 views

Find the minimum capacity edge that is maximized among all paths from $s$ to $t$

Consider some weighted, directed graph $G=(V,E)$. How can we find the edge that is the maximum of all minimum values along paths from $s$ to $t$? For example, if there are two paths from $s$ to $t$ ...
1
vote
1answer
7 views

Prove that there always exists a fair driving schedule

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
1
vote
1answer
25 views

Connections between loops (algebraic structure) and graphs

I would like to know whether there are known constructions which provide a bijection between loops (isomorphism classes) and (possibly directed) graphs. Any reference to a useful paper in this ...
-1
votes
1answer
34 views

Can someone tell me how to solve this problem? [on hold]

Let $G$ be a connected graph with $n$ vertices. Let $GT$ be the graph having the spanning trees of $G$ as vertices, with two vertices $s$ and $t$ being adjacent if and only if the corresponding ...
1
vote
1answer
27 views

Prove that an Eulerian graph $G$ has even size iff $G$ has an even number of vertices $V$ which $\deg(v) \equiv 2\pmod 4$

Prove that an Eulerian graph $G$ has even size iff $G$ has an even number of vertices $V$ which $\deg(v) \equiv 2 \pmod 4$. Let $m=2k$ because $G$ hase even size. So by the first theorem of graph ...
1
vote
4answers
20 views

Prove or disprove if $G$ is 2-edge-connected then there exist 2 edges disjoint $u-v$ trail such that every edge of $G$ lies on one of these trails.

Let $G$ be a connected graph with exactly 2 odd vertices $u$ and $v$ such that $deg(u) \geq 3$ and $deg(v) \geq 3$. Prove or disprove if $G$ is 2-edge-connected then there exist 2 edges disjoint $u-v$ ...
1
vote
1answer
18 views

Find a necessary and sufficient condition for the Cartesian product $G \times H$ is Eulerian, for $G$ and $H$ are non trivial connected graphs.

Find a necessary and sufficient condition for the Cartesian product $G \times H$ is Eulerian, for $G$ and $H$ are non trivial connected graphs. I know that if every vertex in $H$ and $G$ are both odd ...
1
vote
1answer
15 views

Let $F$ and $H$ be 2 disjoint non-Eulerian regular graphs and let $G=(F+K) \bigvee K_1$. Prove that $G$ is Eulerian

Let $F$ and $H$ be 2 disjoint non-Eulerian regular graphs and let $G=(F+H) \bigvee K_1$. Prove that $G$ is Eulerian Here is what I got so far. Let $F$ be a $r-regular$ graph of order $x$ and $H$ be ...