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
1answer
7 views

What are those weighed graphs called?

Let $G = (V, E)$ be a directed graph, and define the weight function $f : V \sqcup E \to \mathbb{R}^+$ as follows: sum of weights of vertices is 1, if a vertex has edges coming out of it, their ...
0
votes
0answers
9 views

Show that a connected $\alpha$-critical graph has-no cut vertices.

A graph is $\alpha$-critical if $\alpha$ (G - e) > $\alpha$ (G) for all e$\in$E. The number of vertices in a maximum independent set of G is called the independence number of G and is denoted by ...
2
votes
1answer
25 views

A bipartite graph like $G(X,Y)$ such that $|X|=|Y|=k$ and $\delta(G) \gt \frac {k}{2}$ is Hamiltonian.

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets $X$ and $Y$ (that is, $X$ and $Y$ are each independent sets) such that every edge connects a vertex in ...
0
votes
1answer
15 views

Prove that in a 2-connected graph like G which has the vertex $v$, $v$ has a neighbor $u$ such that $G-v-u$ is connected

A graph $G$ is said to be $k$-connected (or $k$-vertex connected, or $k$-point connected) if there does not exist a set of $k-1$ vertices whose removal disconnects the graph. Let $v$ be a vertex of ...
0
votes
0answers
9 views

Condition for global cascade

Assume a unidirectional, unweighted network generated according to a degree distribution. Each node is given a value between 0 and 1 called threshold $\phi$. We topple some nodes, the neighbours will ...
0
votes
0answers
8 views

How do I find the edge connectivity from (u,v)?

Also how do you find the vertex connectivity from (u,v), the maximum size of a set of pairwise internally disjoint u,v paths, and the maximum size of a set of pariwise edge-disjoint u,v paths. I got ...
0
votes
0answers
10 views

Number of nodes (or vertices) with degree at most average degree + some constant [on hold]

I'm struggling with a problem of graph theory. In any graph I'm trying to compute how many nodes have degree at most average degree + 1 (or some constant independent of the graph). Obviously there ...
0
votes
0answers
16 views

Is the path from u to v is diameter of the tree?

The diameter of a tree is the longest (simple) path in the tree. Let u be a vertex in a tree and let v be the farthest from u vertex in T. Show that the path from u to v may not be a diameter I am ...
5
votes
2answers
46 views

21 points on circumference of a circle must have at least 100 pairs separated by 120+ degrees.

Prove that at least 100 of the arcs determined by the pairs of these points subtend an angle not exceeding 120 degrees at the center. How do I prove this? Induction? Help please. Thanks.
1
vote
1answer
28 views

a question about the bipartition of a graph

Please,could you help at the following question? Show that if G is a simple graph that has n vertexes,where n>4,then G is bipartite or the complement of G is bipartite. I tried induction,but it ...
0
votes
0answers
17 views

a question about simple graphs 2 [duplicate]

Please,could you help me at the following question? Show that if G is a simple graph that has at least n vertexes,where n>1,then G is connected or the complement of G is connected.
1
vote
1answer
23 views

A question about complete graphs

Please,could you help at the following question? Show that if G is a simple graph that has at least 6 peaks,then G contains a cycle with length 3 or the complement of G contains a cycle with length ...
1
vote
1answer
27 views

Hamiltonian path problem vs other NPC problems

If we can solve the Hamiltonian path in time $O(n^4)$ then you can solve any other NPC problem in $O(n^4)$ time. Is it true of false? I think it is false, even tho Hamiltonian path problem in NPC it ...
0
votes
1answer
19 views

If $G$ is a graph with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$ , then $ \chi'(G) \ge \Delta(G)+1$

We define : $\chi'(G)$ is the minimum number of colors we need in order to color all edges of the graph $G$. Assume that we have a graph like $G$ with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$. ...
0
votes
1answer
28 views

Graph Theory- Visting a vertex

In the complete graph $K_{9}$ choose 2 vertices and call them A and B . Count the number of simple paths (Paths that don't revisit a vertex) between A and B Don't know how to start :/
0
votes
0answers
14 views

Minimal spanning trees in multigraphs with constraints

I have a multigraph G whose edges have three identities. Let's say I have three colors of the edges red, blue and green and each two nodes may be connected by a red, blue and/or green edges. The graph ...
0
votes
1answer
43 views

Can a triangle free graph represent a Group?

Some facts are- Group can be represented by a graph. Quasi Group can be represented by Latin Square matrix, thus by a Latin Square graph. Group Isomorphism $\leq_p$ Graph Isomorphism. Under this ...
1
vote
1answer
13 views

Prove that every triangle-free graph on n vertices has chromatic number at most 2√n.

How do I start the proof? Do I start by creating any triangle free graph or is there a theorem that I need to use?
0
votes
1answer
16 views

how many graphs with vertices $\{a,b,c,d\}$ exist such that each vertex lies in exactly one cycle of length at most $2$?

In a attempt to answer this question I came up with the following answer: This can be asked as a graph theory problem: how many directed graphs with outdegree $1$ and vertices $\{a,b,c,d\}$ exist ...
1
vote
1answer
18 views

How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$: I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since ...
0
votes
1answer
25 views

Literature on generating functions for networks

Are you aware of any material the presents all (or most, or many) the properties and applications of generating functions in the context of graphs? For example I am aware of 'Generating ...
0
votes
1answer
24 views

Simple connected graph question

What is the minimum number of edges that a simple connected graph with n vertices can have? A simple graph means that there is only one edge between any two vertices, and a connected graph means ...
6
votes
3answers
89 views

Minimum number of marked squares on $n × n$ board

Came across this question: Consider an $n × n$ square board, where $n$ is a fixed even positive integer. The board is divided into $n^2$ unit squares. We say that two different squares on the board ...
0
votes
0answers
9 views

Show that $K_{2n+1}$ can be expressed as the union of $n$ connected 2-factors ($n ≥ 1$)

Show that $K_{2n+1}$ can be expressed as the union of $n$ connected 2-factors ($n ≥ 1$) I'm lost, any ideas will help
0
votes
3answers
43 views

Prove that graph with odd number of odd degree vertices does not exist

I need to prove that it is impossible to have a graph in which there are an odd number of odd degree vertices. What is the easiest way to formally prove this? I feel that I can prove it just by ...
0
votes
1answer
12 views

Are there any connected graphs with constant link which are not vertex transitive?

By constant link, I mean for any vertices $v,w$ of a graph $G$, the subgraph of $G$ induced by the neighborhood of $v$ is isomorphic to the subgraph induced by the neighborhood of $w$. $C_n + C_m$ ...
2
votes
0answers
30 views

On combinations of planar graphs of given number of vertices of given valences

Good evening, I am new at the MSE, I signed up just now, so I greet you all; please bare with the newcomer. I have a graph theory problem, which has come up in an entirely different context, a ...
0
votes
0answers
13 views

How to draw K1,3 and C5 as a cartesian product?

I've already drawn a complete bipartite graph with 1 vertex in the 'X' set and 3 vertices in the 'Y' set, but how do I fit the C5 in that graph? I can't picture it. Then how do I find the maximum ...
0
votes
1answer
28 views

Proof in Graph theory, trees

Let $G$ be an acyclic graph with $c$ components. Show that the number of edges of $G$ is $n-c$. I tried to write an indirect proof, but I'm not sure that this is the appropriate way to solve the ...
2
votes
0answers
19 views

Shortest paths on uncountable infinite graph

Lets consider the weighted directed graph $G=(V,E,w)$ where the vertices are $V=[0,1]\subset \mathbb R$ (alternatively $V=(0,1]$ or $(0,1)$), $E = V\times V$ and the weights are given by a function $w ...
0
votes
0answers
9 views

Is cyclomatic number defined “e – n + 1 ” only for connected graphs?

I have read that cyclomatic number is defined as E – N + P. Other sources say that for connected graphs, it is E – N + 1, some say that this applies only to strongly connected graphs. Which is ...
0
votes
1answer
29 views

Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching maxima cardinallity. A tree is an acyclic connected graph. Is there an efficient algorithm ...
1
vote
0answers
11 views

Bipartite graph degree property proof/disproof

Let G be the set of all bipartite graphs. Prove/disprove that there exists some bipartite graph that satisfies the following property: minDeg+maxDeg>|V| where minDeg is the minimal ...
1
vote
0answers
17 views

Is there an algorithm to find minimum cut in undirected graph separating source and sink

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components. I ...
0
votes
1answer
11 views

Relationship between Maximal Independent Set and Minimum Vertex Cover

Prove that $I$ is a Maximal Independent Set of $G(V,E)$ if and only if $V\setminus I$ is a Minimal Vertex Cover of $G(V,E)$. I think that I have managed to prove that the complement of $I$ is a ...
1
vote
0answers
17 views

Proving a game has a winning strategy over a graph $G$ if and only if $G$ has no perfect matching

Two people play a game over a graph $G$ choosing alternately different vertices $v_1,v_2,...$ such that, for every $i>0$, $v_i$ is adjacent to $v_{i-1}$. The last player capable of choosing a ...
0
votes
1answer
29 views

Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors

Suppose we have a graph $M$ such that the max degree of any vertex is $\alpha$. Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors. My attempt I am thinking that I ...
0
votes
0answers
16 views

Suppose G and G' are isomorphic and G has m vertices of degree k. Prove that G' has m vertices of degree k

Suppose G and G' are isomorphic and G has m vertices of degree k. Prove that G' has m vertices of degree k. I don't know how to start this one
0
votes
0answers
6 views

What is the name of the problem domain, solution algorithm of a specific shortest path problem?

I'm trying to find materials for gaining deeper insight in a specific type of a shortest path problem. This is a shortest path problem, where several workers have to service some jobs, each job having ...
0
votes
0answers
7 views

Ranking cliques based on edge weights AND node weights

I am looking for existing methods to rank cliques based on both the edge and nodes weights. Up to now, I was summing up the edges' weights, and I would like to leverage the prior probability I have on ...
0
votes
0answers
19 views

graph without cut vertex such that $i(G)$ > $\frac{n}{2}$

dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a ...
0
votes
0answers
18 views

Connected Graph with Permutation Characterisation

Given a directed graph $G$ with $N$ vertices and adjacency matrix $A$. For any sequence of vertices $s \in \{1,\dots,N\}^k$ with $k>0$, there is a path $p$ in $G$ with $p = P(s)$, where $P$ is a ...
-3
votes
0answers
36 views

Knowing and not knowing [on hold]

Consider a gathering of more than three people. Assume knowing is a symmetric relation i.e if A knows B then B knows A. Given two persons, the number of people they both know is exactly one. Prove ...
0
votes
1answer
25 views

Let G be a graph such that $\delta (G) = n(G) − 2$. Prove that $\kappa (G) = \delta (G)$.

I know if $\delta (G) = n(G) − 1$, $\kappa(G) = \delta(G)$ as $G$ is just a complete graph. But, how do I prove it for $\delta(G) = n(G) − 2$?
0
votes
0answers
14 views

relation between diameter of graph and diameter of its complement [closed]

let $G$ be a regular and connected graph with diameter $3$. Then prove that the diameter of complement of $G$ is $2$.
0
votes
0answers
19 views

Find the Number of cycles of length n in $K_n$ and the cycles of length 2n in $K_n,_n$ . [closed]

Find the number of cycles of length n in a Complete Graph with n Nodes ,denoted as $K_n$ , and the cycles of length 2n in a Bipartite Graph of (n,n) ,denoted as $K_n,_n$.
0
votes
1answer
9 views

Completion of acyclic sub graph

Statement: Given an acyclic subgraph of a connected graph, show that this subgraph can be completed into a spanning tree of the graph. I know that there is a theorem that states that any connected ...
0
votes
1answer
18 views

Proving that any two spanning trees for a graph has the same number of edges

Prove that any two spanning trees for a graph has the same number of edges. Proving by contradiction. Assume that there exists two spanning trees with different number of edges. Take $G$ to be the ...
0
votes
1answer
21 views

Whats the difference between the smallest connected spanning subgraph and a eulerian path?

I personally don't think there is much difference? Apart from for the smallest connected spanning subgraph that the smallest connected subgraph MUST have n-1 edges where n is number of vertices but ...
0
votes
0answers
17 views

Nodes lying on Same Path in Trees

Given a Treen with $n$ nodes and $n-1$ edges, I have to answer $Q$ queries. In every query, I get a list of nodes of size $k$, $n_1, n_2, ..., n_k$. I need to answer the minimum number of paths that ...