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

2
votes
2answers
30 views
0
votes
2answers
36 views

Concept: The graph component

I have the following definition for a Component of a graph: A subgraph $H$ of a graph $G$ is a component of $G$ if $H$ is a maximal connected subgraph of $G$, ...
0
votes
2answers
11 views

Degree of a vertex in following graph.

If I have the following graph : Should the degree of vertex $v_2$ be 1 or 2...I'm asking this because I'm not sure whether loop should be counted while considering degree... (In my notes the ...
1
vote
1answer
30 views

Difference between a sub graph and induced sub graph.

I have the following paragraph in my notes: If $G=(V,E)$ is a general graph . Let $U\subseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ , then ...
6
votes
4answers
1k views

“faces” of a non-planar graph

Good afternoon, I have a question concerning concepts in graph theory. Graph theory is a field quite strange to my knowledge, so my question is maybe stupid. For a planar graph, we can define its ...
0
votes
1answer
26 views

Checking graph is simple or not ,given its degree sequence .

I don't know what is the way to check this: Check whether the graph having degree sequence $\{3,3,1,1\}$ is a simple graph or not? Please help explaining the strategy I must follow to check ...
0
votes
0answers
18 views

Suffix string starting at $i$

$S$ is the string of characters:TACGCGGT$ For string S and each of the positions $i=1,2,\dots,9$ write down the suffix string starting at position $i$. What is ...
2
votes
2answers
376 views
0
votes
0answers
28 views

Show that this algorithm provides a matching of at least this size?

Consider the 'greedy' algorithm for finding a matching on a graph G. First pick an edge xy, add this edge to the matching then delete both x and y from the graph and continue. Suppose that $e(g)\geq ...
0
votes
1answer
23 views

Is the number of simple circuits of a particular length preserved in two isomorphic graphs?

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length? Do they also have to have the same number of such ...
0
votes
1answer
19 views

Need help on an inequality proof

If G is a simple graph containing exactly two components H and H', show that $$|E(G)| \le \frac{(|V(G)|-1)(|V(G)|-2)}{2}$$ Here is my (incomplete) proof that I need help with: 1. Since H and H' are ...
2
votes
2answers
22 views

Determined those positive integers $n$ such that there exists a regular tournament of orders $n$

Determined those positive integers $n$ such that there exists a regular tournament of orders $n$ I know that a tournament is a oriented complete graph, and every complete graph $K_n $ has $ \left( ...
0
votes
1answer
44 views

Which Snake fields can be played infinitely long?

Snake is a very old game for phones. Its a 'real time game', that means you have to make decisions fast. The rules are: You are a snake. You can move to the left, to the right or go straight ahead. ...
0
votes
0answers
24 views

How to find a legal flow in a network with upper and lower bounds?

I am trying to understand Ford-Fulkerson algorithm. How can I use Ford-Fulkerson algorithm to find legal flow and NOT MAX flow.
0
votes
1answer
29 views

How are loops represented in an edge set?

When a node $v_1$ in a graph has an edge to itself (a loop), will this be represented as $\{v_1\}$ or as $\{v_1, v_1\}$?
0
votes
1answer
52 views

A graph with infinitely many distinct cycles

I am trying to show the following statement, but I can't. If a graph contains infinitely many distinct cycles then it contains infinitely many edge-disjoint cycles.
0
votes
0answers
37 views

How to prove this infinite D$_{3\text{h}}$ prism has $0$ volume?

When we build this infinite D$_{3\text{h}}$ prism out of a stack of Nicomachus' triangles and then weight the edges to the differences between the vertices, the prism has $0$ volume. How can we prove ...
0
votes
1answer
40 views

Let $G$ be a simple graph whose vertices of maximum degree $\Delta $ induce a forest. Show that $\chi ^{'}=\Delta$.

Let $G$ be a simple graph whose vertices of maximum degree $\Delta $ induce a forest. Show that $\chi ^{'}=\Delta$. I actually don't understand this question well,is it saying that if we take induced ...
1
vote
1answer
35 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 ...
4
votes
1answer
39 views

$4$-cycle of the same color in $K_n$

Let $k$ be a fixed positive integer. All edges of the complete graph $K_n$ are colored in one of $k$ colors. What is the least $n$ such that there always exists a $4$-cycle of the same color? This ...
0
votes
1answer
21 views

Given a random labelled simple graph with n edges, when is it more likely to get a graph with more edges than vertices?

That is, for what number of vertices n does there exists more simple labelled graphs (with n vertices) with more edges than vertices than simple labelled graphs (with n vertices) with more vertices ...
0
votes
2answers
382 views

what is the maximum number of non loop edges that can exist in an undirected graph

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph. for example if vertices are 10 then how many non loop edges can exist?
28
votes
13answers
9k views

What are good books to learn graph theory?

What are some of the best books on graph theory, particularly directed towards an upper division undergraduate student who has taken most the standard undergraduate courses? I'm learning graph theory ...
1
vote
1answer
28 views

dijkstra's algorithm in time O(k|V|+|E|)

Can somebody can help me with this problem: I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the ...
12
votes
1answer
70 views

What is the minimum number of vertices needed to represent a solid of genus $n$ in $\Bbb R^3$?

The image below shows a $9$-vertex polyhedron that is topologically equivalent to a torus, and hence has genus $1$. ...
3
votes
1answer
886 views

The number of non-isomorphic spanning trees in K4

K4 has 16 spanning trees. I believe there are two non-isomorphic spanning trees in K4. Is this because half of the spanning trees have the sequence (1,2,2,1) as the degrees of their vertices, while ...
0
votes
0answers
15 views

Can I reconstruct Penney's game win probabilities from dominant strategy odds?

The probabilities of each strategy (row in the table below) in Penney's game (assuming the basic version played with a penny — no relation — and strategies consisting of a pattern the outcome of three ...
1
vote
2answers
41 views

Proving Konig-Egervary Theorem from Ford-Fulkerson

I've been going over a proof for Konig-Egervary Theorem from Ford Fulkerson, and I just don't see it. In fact, it just seems false. So I'm not sure what I'm missing. Note: the Konig-Egervary Thm says: ...
2
votes
1answer
40 views

Prove or disprove a statement about $4$ regular graph with orientation

Prove or disprove: there eixsts a $4$-regular graph $G$ of order 7 and an orientation $D$ of $G$ such that for every vertex $u$ of $D$, there eixts either a $u-v$ path of length 1 or a $u-v$ path of ...
3
votes
0answers
30 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
1
vote
2answers
39 views

Connected graph - 5 vertices eulerian not hamiltonian

i need to give an example of a connected graph with at least 5 vertices that has as an Eulerian circuit, but no Hamiltonian cycle?
1
vote
0answers
33 views

Prove that if $r(x)≠r(y)$ for every 2 distinct vertices $x$ and $y$ of $D$ then $D$ contain a Hamiltonian path.

A vertex $v$ in digraph $D$ is said to be reachable. from a vertex $u$ in $D$ if $D$ contains a $u-v$ path. Let $D$ be a digraph and for each vertex $u$ of $D$, let $R(u)$ be the set of vertices ...
0
votes
1answer
43 views

How to prove that no hamiltonian cycle exists in the graph

** Show that the graph below has a hamiltonian path but no hamiltonian cycle. You can find more than one hamiltonian path such as $(b,a,c,f,e,g,d)$. Actually, I tried many times to find a ...
1
vote
1answer
56 views

Pidgeonhole Principle.

Suppose there are 3000 members in each of the club X, Y and Z. Each member from each of these three clubs has at least 3001 friends from the other two clubs altogether. Show that there are three ...
0
votes
1answer
36 views

Prove that wheel (Wn) graph family are hamiltonian

I need to determine and prove that wheel (Wn) graph family are hamiltonian. I know that the Wn graphs are hamiltonian where it's possible to create a cycle that contains all the vertices, but How to ...
0
votes
1answer
36 views

How many trees are in an n-cycle? (graph theory)

I am asked how many trees are in an n-cycle. It doesn't specify that these trees must be spanning trees, just trees. I know the number of trees on n labelled vertices is nexp(n-2), but this isn't ...
1
vote
2answers
17 views

Show that that there exists a digraph $D$ such that both $od(v)$ and $id(v) $ are at least $\frac{n-1}{2}$ but $D$ is not Hamiltonian.

Show that for infinitely many positive integers $n$ that there exists a digraph $D$ of oreder $n$ such that $od(v)≥ \frac{n-1}{2}$ and $id(v)≥ \frac{n-1}{2}$ for every vertex $v$ of $D$ but $D$ is not ...
2
votes
0answers
23 views

Existence of $K_{\log n}$ as minor

As a part of my thesis I have to consider undirected simple bipartite graphs $G = (U, V, E)$ whose edges can be colored with two colors 0 and 1. Such a coloring $\gamma : E \rightarrow \{0,1\}$ of ...
4
votes
5answers
847 views

Short proof for the non-Hamiltonicity of the Petersen Graph

It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either. Is there a simple (short) argument that the ...
0
votes
0answers
28 views

Connected vertex transitive graph with components

Let $G$ be locally finite connected vertex transitive graph and $S$ be a finite set of vertices of $G$ such that $G\setminus S$ has three components. Does exist $id\neq f\in {Aut}(G)$ such that $f(S)$ ...
0
votes
1answer
22 views

Prove that if $G$ is an nontrivial connected graph with at most 2 bridges, then there exists an orientation $D$

According to theorem 3.4, a nontrivial graph G has a strong orientation if and only if G is connected and contain no bridges a)Prove that if $G$ is an nontrivial connected graph with at most 2 ...
0
votes
0answers
18 views

Is there a name for a graph homomorphism that is almost subgraph isomorphic but allows multiple nodes to map to the same node?

I'm looking for a kind of graph homomorphism $f : G = (V_G, E_G) \rightarrow H = (V_H, E_H)$ that is almost the same as subgraph isomorphism, but not quite. I require $f$ to map every node in $V_G$ to ...
20
votes
3answers
487 views

Math puzzle: 10 digit strings generations

There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how ...
1
vote
1answer
46 views

Counting the number of complete bipartite subgraphs

I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
0
votes
0answers
18 views

Proof verification that two spanning tress of the same graph are the same size

Let $H$ be any graph and $T_1$ and $T_2$ be spanning trees for $H$. Prove that the size of $T_1$ equals the size of $T_2$. Proof: $T_1$ has an edge set ...
2
votes
4answers
654 views

What if not connectedness defines a graph?

I am studying graphs through an online course and came across the idea of a "connected component", a "subgraph in which any two vertices are connected to each other by paths, and which is connected to ...
3
votes
1answer
31 views

Serial version of Hall's marriage theorem?

Hall's marriage theorem states that a collection of men can get married iff for every group of $k \geq 1$ men, the total number of women that like one or more of them is at least $k$. For example, if: ...
0
votes
1answer
20 views

Are These Graphs Circulant?

We will say a circulant graph is a graph whose adjacency matrix is circulant (even if the graph is disconnected). Let $R$ be a Dedekind domain, and let $I$ be an ideal of $R$ such that $R/I$ is finite ...
0
votes
1answer
19 views

Orientation digraph question

Let $G$ be nontrivial connected graph without bridge a) show that for every edge $e$ of $G$ and for every orientation of $e$, there exist an orientation of the remaining edges of $G$ such that the ...
2
votes
0answers
25 views

Prove that a graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian

Prove that a graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian Here is what I got so far. => Let $G$ has an Eulerian Orientation, then $G$ is an Eulerian digraph. For any digraph ...